Rekurencja czy iteracja?
🎯 Po co Ci to?
Masz teraz dwa narzędzia na to samo: pętlę i rekurencję. Kiedy które? To nie kwestia gustu — to decyzja inżynierska o realnych konsekwencjach: czytelności, szybkości, a czasem o tym, czy program w ogóle się nie wysypie. W tej jednostce nauczysz się wybierać świadomie — a punktem zwrotnym będzie ponowne spotkanie z Fibonaccim, który raz jest wzorem elegancji, a raz katastrofą, w zależności od tego, jak go napiszesz.
✅ Czego się nauczysz
Po tej jednostce potrafisz:
- przełożyć prostą rekurencję na iterację i odwrotnie;
- rozpoznać po kształcie drzewa wywołań, czy rekurencja jest tania (łańcuch), czy droga (rozgałęzienie);
- wybrać właściwe narzędzie, ważąc czytelność, głębokość stosu i powtarzanie pracy.
🔁 Przypomnij sobie
Z 4.3: Fibonacci iteracyjnie (okno) i rekurencyjnie (drzewo, wykładniczy koszt); z 7.1: głębokość stosu i jego granica.
📘 Wyjaśnienie
Każda pętla to rekurencja i odwrotnie — to fakt teoretyczny (dwa oblicza tej samej mocy obliczeniowej). Ale w praktyce jedno bywa dużo lepsze od drugiego, i decyduje o tym kształt drzewa wywołań.
Rekurencja łańcuchowa (każde wywołanie woła co najwyżej jedno): silnia, suma, odwracanie napisu. Drzewo to prosty patyk. Taką rekurencję trywialnie zamienia się na pętlę — i zwykle należy, bo pętla nie obciąża stosu:
def silnia_iter(n):
wynik = 1
for i in range(1, n + 1):
wynik = wynik * i
return wynik
Ta sama praca, zero ryzyka RecursionError, często odrobinę szybciej (brak kosztu wołania funkcji). Dla łańcuchowych rekurencji iteracja to zwykle lepszy wybór produkcyjny — rekurencji używa się wtedy dla czytelności albo gdy problem jest z natury rekurencyjny (drzewa, katalogi).
Rekurencja rozgałęziona (wywołanie woła kilka): tu robi się ciekawie — i groźnie. Wróć do naiwnego Fibonacciego z 4.3:
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2) # DWA wywołania — drzewo się rozgałęzia!
Drzewo rozrasta się wykładniczo, a co gorsza — te same podproblemy liczą się wielokrotnie (fib(3) policzy się dwa razy, przy fib(10) już 55 razy). To jest zła rekurencja: nie dlatego, że rekurencyjna, tylko dlatego, że marnuje pracę. Wersja iteracyjna z oknem (4.3) robiła to w $n$ krokach.
Ale czy rozgałęzienie zawsze skazuje na porażkę? Nie! Scalanie (6.6) też się rozgałęzia (dwa wywołania na połówki) — a jest szybkie. Różnica jest fundamentalna: u scalania każde wywołanie dostaje inne, rozłączne dane (lewa i prawa połowa), więc żaden podproblem się nie powtarza; u Fibonacciego wywołania nachodzą na siebie (fib(n-1) i fib(n-2) oba potrzebują fib(n-2)). To rozstrzyga wszystko:
📐 Reguła doboru: rekurencja jest tania, gdy podproblemy są rozłączne (dziel i zwyciężaj: scalanie, szybkie, binarne) — drzewo pracuje raz nad każdym kawałkiem. Rekurencja jest droga, gdy podproblemy się powtarzają (naiwny Fibonacci) — wtedy albo iteruj, albo zapamiętuj już policzone wyniki (o tym w dziale 8: programowanie dynamiczne).
💭 Pomyśl: Silnia i naiwny Fibonacci to obie rekurencje. Czemu silnia jest w porządku, a Fibonacci to katastrofa — skoro obie „wołają siebie"?
Sprawdź odpowiedź
Silnia woła jedno (silnia(n-1)) — drzewo to patyk, każdy podproblem raz, koszt liniowy (a jedyna wada to głębokość stosu — leczona iteracją). Fibonacci woła dwa i te dwa się zazębiają — drzewo gęstnieje wykładniczo z krotnym liczeniem tego samego. Liczba wywołań, nie samo słowo „rekurencja", decyduje o losie. Patrz zawsze na kształt drzewa: patyk — spokój; rozłączne gałęzie — dobrze; nachodzące gałęzie — uciekaj (do iteracji albo do zapamiętywania).
🐞 Znajdź błąd
Student „optymalizuje" sumę cyfr liczby, pisząc ją rekurencyjnie:
def suma_cyfr(n):
return n % 10 + suma_cyfr(n // 10)
Dla suma_cyfr(123) liczy 1+2+3… i pada. Znajdź brak i dopisz — a potem oceń: czy ta rekurencja jest „dobra" (warto ją zostawić), czy lepiej iterować?
Sprawdź odpowiedź
Brak bazy: gdy n spadnie do 0 (123 → 12 → 1 → 0), krok woła suma_cyfr(0 // 10) = suma_cyfr(0) bez końca. Naprawa: if n == 0: return 0 na początku. Ocena: to rekurencja łańcuchowa (jedno wywołanie), głębokość = liczba cyfr — czyli dla liczb realistycznych najwyżej kilkanaście poziomów. Bezpieczna i czytelna, więc można zostawić (choć pętla while n > 0: s += n % 10; n //= 10 jest równie dobra). Reguła: łańcuchowa + płytka = wolny wybór; rozgałęziona z powtórkami = zmień podejście.
⚠️ Uwaga, pułapka
„Rekurencja jest elegancka, więc lepsza" to półprawda, która kosztowała niejeden zawieszony program. Elegancja kodu i jego wydajność to osobne kryteria (jak w 6.5: krótszy ≠ szybszy). Naiwny Fibonacci jest prześliczny i bezużyteczny. Przy wyborze narzędzia pytaj po kolei: (1) czy problem jest z natury rekurencyjny (drzewo, katalog)? (2) czy głębokość jest bezpieczna (logarytmiczna/mała, nie liniowa-ogromna)? (3) czy podproblemy się nie powtarzają? Trzy „tak" — bierz rekurencję śmiało. Jakieś „nie" — iteruj albo zapamiętuj.
🛠️ Teraz Ty
Bez komputera: narysuj drzewa wywołań fib(5) (rozgałęzione) i silnia(5) (patyk) obok siebie — policz węzły w każdym. Z komputerem: dodaj do naiwnego fib globalny licznik wywołań i zmierz go dla $n$ = 10, 20, 30 (przygotuj się na szok). Potem napisz fib_iter i porównaj czasy dla $n = 35$.
📐 Definicje tej lekcji
- Rekurencja łańcuchowa / rozgałęziona — jedno wywołanie na poziom (patyk) / kilka (drzewo).
- Podproblemy rozłączne / nachodzące — dane wywołań nie/pokrywają się; decyduje o tym, czy rozgałęzienie jest tanie.
- Reguła doboru — łańcuch płytki: wolny wybór; rozłączne rozgałęzienie: rekurencja świetna; nachodzące: iteruj lub zapamiętuj.
📌 Najważniejsze w pigułce
- Każdą rekurencję da się iterować; kształt drzewa wywołań mówi, czy warto.
- Łańcuch → zwykle iteruj (stos); rozłączne gałęzie → rekurencja błyszczy; nachodzące gałęzie → katastrofa.
- Elegancja ≠ wydajność; wybieraj po głębokości i powtarzaniu pracy, nie po urodzie kodu.
🎒 Zadania
- Sklasyfikuj rekurencje jako łańcuchowe/rozgałęzione i oceń, czy warto je zostawić: (a) Euklides (4.2), (b) naiwny Fibonacci, (c) scalanie (6.6), (d) szybkie potęgowanie (4.6).
Wskazówka i odpowiedź
(a) łańcuchowa, głębokość logarytmiczna (reszta szybko maleje) — świetna. (b) rozgałęziona z powtórkami — katastrofa, iteruj. (c) rozgałęziona, podproblemy rozłączne, głębokość $\log n$ — wzorcowa. (d) łańcuchowa (jedno wywołanie na poziom po w = potega(n//2)), głębokość $\log n$ — świetna. Wniosek: „rozgałęziona" nie jest wyrokiem (c jest świetna), a „łańcuchowa" nie jest gwarancją (silnia bywa za głęboka) — liczy się głębokość i powtórki razem.
- Przełóż na iterację rekurencję
def licz(n): return 0 if n == 0 else 1 + licz(n // 2)(liczy… co właściwie?). Co ta funkcja oblicza?
Wskazówka i odpowiedź
Liczy, ile razy da się podzielić $n$ przez 2 do zera — czyli (prawie) $\lfloor \log_2 n \rfloor + 1$, liczbę bitów $n$! Iteracyjnie: c = 0; while n > 0: c += 1; n //= 2; return c. Rozpoznajesz? To metoda zamiany na system dwójkowy (2.1) w przebraniu — liczenie kroków połowienia. Ta sama operacja przewija się przez całą książkę, raz jako konwersja, raz jako logarytm, raz jako głębokość rekurencji.
- Kiedy zamiana rekurencji na iterację jest trudna (wymaga własnego stosu, a nie prostej pętli)? Podaj rodzaj problemu i wyjaśnij dlaczego.
Wskazówka i odpowiedź
Gdy rekurencja jest rozgałęziona i musisz odwiedzić obie gałęzie — np. przejście drzewa katalogów albo scalanie. Prosta pętla przechodzi po jednym wymiarze; żeby ręcznie zasymulować „wejdź w lewe poddrzewo, potem wróć i wejdź w prawe", musisz sam pamiętać, gdzie wrócić — czyli odbudować stos wywołań jako własną strukturę danych (stos z działu 9!). Dlatego dla problemów z natury drzewiastych rekurencję zwykle się zostawia: język daje stos za darmo, ręczna iteracja tylko go odtwarza, brzydziej. To domyka regułę: iteruj łańcuchy, zostaw drzewa.
🔍 Sprawdź, czy umiesz
- Przełożyć łańcuchową rekurencję na pętlę i uzasadnić, że warto.
- Ocenić rekurencję po drzewie wywołań: patyk / rozłączne gałęzie / nachodzące gałęzie.
- Wybrać narzędzie, ważąc czytelność, głębokość stosu i powtarzanie pracy.