Rekurencja w różnych kontekstach — Fibonacci, fraktale i stos wywołań

Po co się tego uczymy?

Rekurencja pojawiała się już wcześniej w tym dziale (wyszukiwanie binarne, MergeSort, szybkie potęgowanie) — czas zrozumieć ją dogłębnie: jak DOKŁADNIE działa "pod maską" (stos wywołań), gdzie w życiu codziennym się pojawia, i dlaczego niektóre jej zastosowania (jak naiwny ciąg Fibonacciego) są zaskakująco wolne — co bezpośrednio prowadzi do tematu programowania dynamicznego (kolejna lekcja).

Teoria

Rekurencja (łac. "recurrere" — powracać) to sytuacja, w której coś ODWOŁUJE SIĘ SAMO DO SIEBIE. W informatyce: funkcja, która wywołuje samą siebie, aż do osiągnięcia PROSTEGO przypadku (tzw. warunku bazowego/końcowego) — bez niego rekurencja nigdy by się nie zakończyła.

Rekurencja w codziennym życiu — rosyjska matrioszka (każda lalka kryje mniejszą kopię samej siebie), gałąź drzewa (z jednej wyrastają mniejsze, z nich jeszcze mniejsze), fraktale (wzory powtarzające się w nieskończoność), lustro w lustrze, a nawet planowanie ("żeby pomalować pokój, muszę kupić farbę, żeby kupić farbę, muszę pojechać do sklepu...") — każdy krok to mniejsze zadanie w obrębie większego.

Przykład — silnia (faktorial): 5! = 5 × 4 × 3 × 2 × 1. Zamiast pętli, funkcja "powtarza się" sama: silnia(n) = n * silnia(n-1), z warunkiem bazowym silnia(0) = silnia(1) = 1.

Przykład — ciąg Fibonacciego: każdy kolejny element to suma dwóch poprzednich: 0, 1, 1, 2, 3, 5, 8, 13.... Rekurencja pasuje tu naturalnie: fib(n) = fib(n-1) + fib(n-2). Każde wywołanie fib(n) uruchamia DWA kolejne — fib(n-1) i fib(n-2) — tworząc drzewo wywołań, które rozgałęzia się, aż dojdzie do podstawy (0 i 1).

Rekurencja a stos (bardzo ważne do zrozumienia!) — za każdym razem, gdy funkcja wywołuje samą siebie, komputer ODKŁADA jej dane na STOSIE — pamięci, gdzie trzyma wszystkie "niedokończone wywołania", czekające na wynik wywołania głębszego. Dopiero gdy dojdzie do warunku bazowego, stos zaczyna się "rozpakowywać" — każdy poziom wraca z wynikiem do poprzedniego, aż dotrze z powrotem do pierwszego wywołania.

Gdzie spotkasz rekurencję w prawdziwym świecie: w grach komputerowych (generowanie drzew, map, labiryntów), w grafice (fraktale, płatki śniegu, symetrie), w wyszukiwaniu (przeszukiwanie folderów, drzew plików), w sztucznej inteligencji (drzewa decyzji), w matematyce (rozwiązywanie równań przez dzielenie problemu na mniejsze).

Najczęstsze błędy przy rekurencji: brak warunku końcowego (program zapętli się w nieskończoność), zbyt głęboka rekurencja (komputerowi zabraknie pamięci stosu — błąd RecursionError), zbyt ogólne myślenie (rekurencja ZAWSZE musi zmierzać do PROSTSZEGO problemu, inaczej się nie zakończy).

Schemat

SCHEMAT OGÓLNY:
FUNKCJA()
 └── robi coś
 └── woła samą siebie z PROSTSZYM zadaniem
 └── aż dojdzie do NAJPROSTSZEGO przypadku (warunek bazowy)

SILNIA(5) - jak stos "rozwija się" i "zwija":
silnia(5)
 → czeka na silnia(4)
    → czeka na silnia(3)
       → czeka na silnia(2)
          → czeka na silnia(1)
             → zwraca 1                    ← DNO stosu, zaczyna się "rozpakowywanie"
          → zwraca 2 * 1 = 2
       → zwraca 3 * 2 = 6
    → zwraca 4 * 6 = 24
 → zwraca 5 * 24 = 120

FIBONACCI - drzewo wywołań rozgałęzia się (fib(4)):
              fib(4)
           /         
       fib(3)         fib(2)
      /              /     
  fib(2)   fib(1)  fib(1)  fib(0)
  /    
fib(1) fib(0)

Przykład z życia

Foldery w komputerze mogą zawierać podfoldery, które z kolei zawierają kolejne podfoldery — program przeszukujący cały dysk w poszukiwaniu pliku (np. wyszukiwarka Windows) używa REKURENCJI: "przeszukaj ten folder, a dla każdego podfolderu zrób DOKŁADNIE to samo". Struktura się powtarza w mniejszej skali — to właśnie rekurencja w praktyce.

rekurencja_podstawy.py

# Najprostszy przykład - odliczanie
def odliczanie(n):
    if n == 0:
        print("Start!")
    else:
        print(n)
        odliczanie(n - 1)

odliczanie(5)
# Wynik: 5 4 3 2 1 Start!


# Silnia (faktorial)
def silnia(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * silnia(n - 1)

print(silnia(5))
# Wynik: 120

fibonacci.py

# Ciąg Fibonacciego - rekurencja z DWOMA wywołaniami samej siebie
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

for i in range(8):
    print(fib(i), end=" ")
# Wynik: 0 1 1 2 3 5 8 13

Komentarz i wyjaśnienie kodu

W odliczanie() zwróć uwagę, że instrukcja print(n) wykonuje się PRZED wywołaniem rekurencyjnym — dlatego liczby wypisują się w kolejności malejącej (5,4,3,2,1), a "Start!" na końcu, gdy osiągnięty zostanie warunek bazowy n == 0.

fib() to CELOWO "naiwna" implementacja pokazująca WADĘ prostej rekurencji: fib(5) wywołuje fib(4) i fib(3), ale fib(4) WEWNĘTRZNIE znowu wywołuje fib(3) — te same wartości są liczone WIELOKROTNIE, co przy większych n (np. fib(35)) sprawia, że program staje się dramatycznie wolny. To dokładnie problem, który rozwiąże programowanie dynamiczne w kolejnej lekcji.

Ćwiczenie samodzielne

Uruchom silnia(5) i narysuj na kartce, jak "rozwija się" stos wywołań (jak w diagramie). Następnie uruchom fib(i) dla i od 0 do 10 i zaobserwuj, jak szybko rośnie czas obliczeń przy większych wartościach (spróbuj fib(30) — zauważysz zauważalne opóźnienie).

Zadania do pracy własnej

Napisz funkcję rekurencyjną, która wypisze liczby od 1 do n (w kolejności rosnącej, w przeciwieństwie do przykładu odliczanie).
Napisz funkcję rekurencyjną suma(n), która zwróci sumę liczb od 1 do n. Następnie przerób funkcję silnia tak, żeby wypisywała KAŻDY krok obliczeń (np. "5 * silnia(4)", "4 * silnia(3)"...).
Zapisz fib(n) BEZ rekurencji, używając zwykłej pętli (przechowując dwie ostatnie wartości ciągu). Zmierz czas działania obu wersji dla n = 30 (moduł time) i porównaj — o ile szybsza jest wersja iteracyjna? Dla chętnych: narysuj CAŁE drzewo wywołań funkcji fib(5) i policz, ile razy wywoływana jest fib(1).

Typowe błędy

Brak warunku bazowego — program zapętli się w nieskończoność (a właściwie wyrzuci błąd RecursionError, gdy przekroczy maksymalną głębokość stosu Pythona, domyślnie ok. 1000 wywołań).

Zbyt głęboka rekurencja dla dużych danych — nawet z poprawnym warunkiem bazowym, rekurencja dla bardzo dużych n (np. silnia(10000)) może wyczerpać limit głębokości stosu; w takich przypadkach lepsza jest wersja iteracyjna (pętla).

Naiwna rekurencja bez zapamiętywania wyników (jak fib() w tym przykładzie) — prowadzi do WYKŁADNICZEJ liczby powtórzonych obliczeń tych samych wartości; rozwiązaniem jest programowanie dynamiczne (memoizacja) z kolejnej lekcji.

Nawiązanie do egzaminu zawodowego

Ten "naiwny" ciąg Fibonacciego jest CELOWYM wprowadzeniem do kolejnej lekcji — programowania dynamicznego, które rozwiązuje dokładnie ten problem (powtarzające się obliczenia) przez ZAPAMIĘTYWANIE (memoizację) już policzonych wartości.