Rekurencją jest dla wielu osób jak magia. Tak więc dzisiaj postaramy się nauczyć Cię magii, czyli stać się magikiem 🙂

Z rekurencją mamy do czynienia, w tedy, kiedy funkcja wywołuje samą siebie.

Bardzo wiele przykładów rekurencji opartych jest o ciąg fibonacciego. Nie jestem przekonany czy to dobrze. Po pierwsze, tworzy to złudzenie że rekurencja jest czymś co używa się przy rozwiązywaniu problemów matematycznych. A po drugie, wiele osób nie ma ochoty uczyć się co to jest ciąg fibonacciego.

My użyjemy innych przykładów aby pokazać czym jest rekurencja, a następnie zadamy sobie pytanie kiedy i gdzie warto ją stosować

Prosty przykład rekurencji (rekursji) w Python

Naszym zadaniem jest napisać funkcję która przyjmuje jako parametr liczbę dodatnią, a następnie ma wrócić sumę wszystkich liczb mniejszych równych podana liczba.

Rozwiązanie z użyciem pętli

def suma_for(liczba):
    suma = 0
    for i in range(liczba + 1):
        suma += i

    return suma

Rozwiązanie z użyciem rekurencji w Python

def suma_rekurencja(liczba):
    if liczba == 0: return 0
    return liczba + suma_rekurencja(liczba - 1)

Rozwiązanie z pętlą chyba nie wymaga tłumaczenia. Ale rozwiązanie z rekurencją jest o wiele ciekawsze. Funkcja zwraca podaną liczbę plus to co sama zwróci jeżeli zmniejszymy liczbę o jeden plus to co sama zwróci jeżeli ponownie zmniejszymy liczbę o 1.

Jeżeli liczba osiągnie wartość 0, to funkcja się dalej nie wykonuje.

Czy jeżeli wywołamy naszą funkcję z wartością 3 – suma_rekurencja(3), To zostanie wykonane następujące wyliczenie:

3 + suma_rekurencja(2), czyli

3 + 2 + suma_rekurencja(1), czyli

3 + 2 + 1 + suma_rekurencja(0), czyli

3 + 2 + 1 + 0

i otrzymamy 6

Kiedy używa się rekurencji

Generalnie, za pomocą funkcji rekurencyjnych, możemy zastąpić każdą pętlę. Ale również każdą funkcję rekurencyjną możemy zastąpić pętlami.

Działanie rekurencji jest o wiele trudniejsze do wyobrażenia sobie i wymaga przyzwyczajenia, wprawy, aby zacząć myśleć funkcjami rekurencyjnymi zamiast pętlami. Wielu programistów ich nigdy nie stosuje i nie potrzebuje.

JEDNAK czasami problem może okazać się o wiele łatwiejszy do rozwiązania z użyciem rekurencji. W szczególności jeżeli możemy go łatwo rozbić na mniejsze, takie same problemy. Tak jak w powyższym przykładzie. Pętla liczyła sumę po kolei. Natomiast rekurencja rozbiła problem na mniejsze problemy. Na końcu tylko zsumowała wszystkie wyniki.

Drzewo rysowane przez funkcję rekurencyjną

Spójrzmy na proste drzewo zrobione w Python Turtle.

Jeżeli przyjrzymy się mu bliżej, skała się z potwarzalnych elementów.

  1. Jest rysowana linia
  2. Na końcu linii jest rozgałęzienie w lewo oraz w prawo, rysowane są linie i ponownie są rozgałęzienia w lewo oraz w prawo
  3. Rysowanie kończy się po siódmym elemencie

Jest ono bardzo proste do zrobienia przy użyciu rekurencji:

import turtle

t = turtle.Turtle()
t.speed(-1)
t.setheading(90)
t.penup()
t.goto(0,-200)
t.pendown()

def gałąź(t, len):

    if len == 0: return

    nt = t.clone()
    nt.forward(50)

    nt.left(20)
    gałąź(nt,len-1)

    nt.right(40)
    gałąź(nt,len-1)
    
gałąź(t, 7)

window = turtle.Screen()
window.exitonclick()
  1. Definiujemy funkcję gałąź
  2. Zadanie funkcji jest banalne. Rysuje gałąź o długości 50
  3. Następnie przestawia żółwia w lewo o 20 stopni, i wywołuje samą siebie, aby narysować linię w lewo
  4. Następnie przestawia żółwia w prawo o 40 stopni, i wywołuje samą siebie, aby narysować linię w prawo
  5. Jako parametry, mamy przekazywanego żółwia oraz długość drzewa jaka została do narysowania
  6. W momencie kiedy długość osiągnie 0, funkcja się nie wykonuje

Można powiedzieć że mamy do czynienia w niewiarygodnie leniwą funkcją. jedyne co robi to rysuje jedną gałąź, a resztę każe narysować innym funkcjom.

I na tym polega, między innymi, piękno rekurencji.

Zliczenie plików na dysku

Innym ciekawym problemem jest policzenie liczby plików na dysku. W głównym katalogu mamy x plików oraz y katalogów. Możemy oczywiście napisać funkcję która używa pętli aby wszystko zliczyć, ale o ile jest to łatwiejsze z użyciem rekurencji? Wystarczy napisać funkcję, która zlicza pliki, a jak napotka katalog, to wywołuje samą siebie z nazwą tego katalogu.

Analogicznie w przypadku web scrapingu. Podajemy adres URL, funkcja zaczytuje zawartość strony. W momencie kiedy napotka inny URL, to wykonuje samą siebie z nowym URL.

Podsumowując

Jedni ją nienawidzą, inni kochają. Są języki programowania które w ogóle nie mają pętli, a jedynie funkcje rekurencyjne jak Haskell. Na pewno nie jest tak intuicyjna jak pętle. Czy trzeba ją znać? NIE. Czy warto ją znać? TAK.

A na końcu, stary suchar: Aby zrozumieć rekurencję, trzeba zrozumieć rekurencję.

Kod drzewa z początku artykułu

import turtle
import random

t = turtle.Turtle()
t.speed(0)
t.setheading(90)
t.penup()
t.goto(0,-200)
t.pendown()


def gałąź(t, len):
    if len == 0: return
    nt = t.clone()
    nt.pensize(len*3)
    if len < 3:
        nt.color('green')
        nt.forward(50)
        if random.randint(0,2) in (1,2):
            nt.begin_fill()
            if random.randint(0,10) == 10: nt.color('red')
            nt.circle(20)
            nt.end_fill()
    elif len < 6:
        nt.color('brown')
        nt.forward(50)
    else: nt.forward(50)
    nt.left(20)
    gałąź(nt,len-1)
    
    nt.right(40)
    gałąź(nt,len-1)
    
gałąź(t, 8)

t.penup()
t.goto(-100,-250)
t.write("Analityk.Edu.Pl", font=("Arial",20,"bold"))

window = turtle.Screen()
window.exitonclick()

Drzewo

programowanie funkcyjne (functional programing)

loops vs recursions

Big Data, Haskell, Scala

Facebook Comments