Funkcja, która woła samą siebie

🎯 Po co Ci to?

Stań między dwoma lustrami — zobaczysz siebie, w sobie, w sobie, coraz mniejszego, aż do znikania. To rekurencja w czystej postaci: obraz, który zawiera własną pomniejszoną kopię. W programowaniu ten sam pomysł pozwala funkcji rozwiązać problem, powołując się na siebie dla mniejszego przypadku. Brzmi jak wąż zjadający własny ogon — ale gdy dorzucisz jeden warunek (kiedy przestać), z pozornego paradoksu rodzi się metoda tak potężna, że część problemów po prostu nie ma rozsądnego rozwiązania bez niej.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• napisać funkcję rekurencyjną z poprawnym przypadkiem bazowym i krokiem;
• prześledzić wykonanie rekurencji, rozumiejąc, co dzieje się na stosie wywołań;
• rozpoznać dwa błędy śmiertelne: brak przypadku bazowego i krok, który nie zmniejsza problemu.

🔁 Przypomnij sobie

Z 1.4: myślenie rekurencyjne = rozwiąż problem jego mniejszą kopią; z 3.5: funkcja, return, zmienne lokalne żyją tylko na czas wywołania; z 4.3: przypadek bazowy jako fundament.

📘 Wyjaśnienie

Zacznijmy od klasyka — silnia: $n! = 1 \cdot 2 \cdot 3 \cdots n$. Definicja iteracyjna to pętla mnożąca. Ale spójrz na $n!$ inaczym okiem: $5! = 5 \cdot 4!$, a $4! = 4 \cdot 3!$… Silnia zawiera własną mniejszą kopię. To zaproszenie do rekurencji:

def silnia(n):
    if n == 0:              # przypadek bazowy: 0! = 1 (umowa matematyczna)
        return 1
    return n * silnia(n - 1)     # krok: mniejszy problem, sklejony mnożeniem

Dwie części — i obie są konieczne:

📐 DEFINICJA — funkcja rekurencyjna: funkcja wywołująca samą siebie, złożona z przypadku bazowego (rozwiązanie wprost, bez dalszej rekurencji) i kroku rekurencyjnego (rozwiązanie przez wywołanie na mniejszym przypadku).

Po ludzku: schody, po których schodzisz w dół (krok), aż dojdziesz do parteru (baza) — i dopiero stamtąd wracasz. Czym NIE jest: pętlą przebraną za funkcję. Rekurencja nie „powtarza" — ona odkłada pracę na później i wykonuje ją przy powrocie ze schodów.

Co się naprawdę dzieje? Prześledź silnia(3) uważnie — to najważniejsze śledzenie w dziale:

silnia(3): potrzebuję silnia(2), czekam...        ┐ odkładam „× 3"
  silnia(2): potrzebuję silnia(1), czekam...      │ odkładam „× 2"
    silnia(1): potrzebuję silnia(0), czekam...    │ odkładam „× 1"
      silnia(0): baza! zwracam 1                   ┘ dno — zaczynam wracać
    silnia(1): dostałem 1, zwracam 1 × 1 = 1
  silnia(2): dostałem 1, zwracam 2 × 1 = 2
silnia(3): dostałem 2, zwracam 3 × 2 = 6

Zauważ dwie fazy: schodzenie (każde wywołanie odkłada swoją pracę „× n" i woła głębiej) i wracanie (od dna, każde dokańcza odłożone mnożenie). Miejsce, gdzie komputer trzyma te odłożone zadania, nazywa się stosem wywołań — to sterta zawieszonych funkcji, każda czeka na wynik tej pod nią. Górna zawsze wraca pierwsza. (Stos jako strukturę danych poznasz w dziale 9 — tu spotykasz go w naturze, jako mechanizm samego języka.)

💭 Pomyśl: Co się stanie, gdy wywołasz silnia(-1)? Prześledź dwa-trzy kroki.

Sprawdź odpowiedź

$-1 \ne 0$, więc krok: -1 * silnia(-2); potem silnia(-3), silnia(-4)… Problem rośnie zamiast maleć — nigdy nie trafi w bazę n == 0. Stos rośnie bez końca, aż Python przerwie: RecursionError: maximum recursion depth exceeded. To rekurencyjny bliźniak pętli nieskończonej (3.3): tam warunek nie gasł, tu baza jest nieosiągalna. Lekarstwo: krok musi zawsze przybliżać do bazy — a specyfikacja (dział 1!) powinna wykluczyć $n < 0$ albo dodać osłonę if n < 0: ....

🐞 Znajdź błąd

Funkcja ma sumować liczby od 1 do $n$:

def suma(n):
    return n + suma(n - 1)

Dla suma(3) program pada. Czego brakuje i jak to naprawić?

Sprawdź odpowiedź

Brak przypadku bazowego. suma(3) = 3 + suma(2) = 3 + 2 + suma(1) = … + suma(0) = … + suma(-1) = … — schodzenie bez dna, RecursionError. Naprawa: if n == 0: return 0 na początku. Reguła żelazna (z 4.3, teraz z naciskiem): najpierw pisz bazę, potem krok — funkcja rekurencyjna bez bazy to nie „prawie gotowa", to „na pewno zepsuta". Każda rekurencja, którą napiszesz w życiu, zacznie się od pytania „kiedy przestaję?".

⚠️ Uwaga, pułapka

Stos wywołań ma skończoną wysokość (w Pythonie domyślnie ~1000 poziomów). Poprawna rekurencja, która schodzi bardzo głęboko — np. silnia(100000) — wysypie się na RecursionError mimo braku błędu logicznego! To nie usterka Twojego kodu, tylko fizyczna granica stosu. Dlatego głębokie „łańcuchowe" rekurencje (jak silnia czy suma) w praktyce zamienia się na pętle — o czym cała następna jednostka. Rekurencja świeci tam, gdzie głębokość jest mała (logarytmiczna, jak w scalaniu), a nie tam, gdzie jest liniowa.

🌍 Powiązania

Rekurencja mieszka wszędzie, gdzie coś zawiera własną kopię: katalog na dysku zawiera podkatalogi (a te — kolejne), zdanie zawiera zdania podrzędne (gramatyka!), a definicja wyrażenia matematycznego zawiera wyrażenia. Dlatego przeglądanie drzewa katalogów, parsowanie języka i obliczanie wyrażeń to naturalnie rekurencyjne zadania — pętla by się tu męczyła, rekurencja tańczy. Rozpoznasz też rekurencję w sztuce (obrazy Eschera), w naturze (rozgałęzienia drzewa, płatek śniegu) i w żartach informatyków („rekurencja: patrz «rekurencja»").

🛠️ Teraz Ty

Bez komputera: prześledź silnia(4) rysując stos (schodzenie i wracanie). Z komputerem: napisz rekurencyjnie (a) suma(n) (1+…+n), (b) potega(a, n) naiwnie ($a^n = a \cdot a^{n-1}$), (c) dlugosc(napis) bez użycia len (podpowiedź: napis to pierwszy znak + reszta; baza — napis pusty). Dla każdej wskaż bazę i krok, zanim napiszesz.

📐 Definicje tej lekcji

• Funkcja rekurencyjna — woła samą siebie; przypadek bazowy (stop) + krok rekurencyjny (mniejszy problem).
• Stos wywołań — sterta zawieszonych wywołań czekających na wynik; górne wraca pierwsze.
• Głębokość rekurencji — długość łańcucha wywołań; ograniczona rozmiarem stosu.

📌 Najważniejsze w pigułce

• Rekurencja = baza + krok; bez bazy schodzisz bez dna (RecursionError), bez zmniejszania — tak samo.
• Wykonanie ma dwie fazy: schodzenie odkłada pracę na stos, wracanie ją dokańcza.
• Stos jest skończony — głębokie łańcuchowe rekurencje zamieniaj na pętle.

🎒 Zadania

1. Prześledź potega(2, 4) dla def potega(a, n): return 1 if n == 0 else a * potega(a, n-1). Ile wywołań, jaka maksymalna głębokość stosu?

Wskazówka i odpowiedź

Wywołania: potega(2,4) → (2,3) → (2,2) → (2,1) → (2,0)=1; wracanie: 2·1=2, 2·2=4, 2·4=8, 2·8=16. Pięć wywołań, głębokość 5 (wszystkie naraz na stosie w momencie dna). To rekurencja łańcuchowa (każde woła dokładnie jedno) — głębokość rośnie liniowo z $n$, więc potega(2, 100000) by się wysypała. Porównaj z szybkim potęgowaniem (4.6): tam głębokość była logarytmiczna — i to jest różnica między rekurencją, która się skaluje, a tą, która nie.

2. Napisz rekurencyjnie funkcję odwracającą napis (odwroc("kot") → "tok"). Wskaż bazę, krok i prześledź dla „abc".

Wskazówka i odpowiedź

Baza: napis pusty (albo jednoznakowy) — odwrócenie to on sam. Krok: odwroc(reszta) + pierwszy_znak. def odwroc(s): return s if len(s) <= 1 else odwroc(s[1:]) + s[0]. Dla „abc": odwroc("bc")+"a" = (odwroc("c")+"b")+"a" = ("c"+"b")+"a" = "cba". Porównaj z pętlowym odwracaniem z 3.4 — ten sam wynik, inna dusza: pętla budowała od przodu, rekurencja skleja przy powrocie ze schodów.

3. Rozważ def tajemnica(n): print(n); if n > 1: tajemnica(n // 2). Co wypisze tajemnica(20)? Jaka jest głębokość rekurencji dla tajemnica(1000000)?

Wskazówka i odpowiedź

tajemnica(20): 20, 10, 5, 2, 1 — pięć linii (połowienie!). Głębokość dla miliona: $\lfloor \log_2 10^6 \rfloor + 1 = 20$. Ta rekurencja połowi argument, więc głębokość jest logarytmiczna — bezpieczna nawet dla ogromnych $n$ (dla trylona: ~40 poziomów). Rekurencje połowiące (jak ta, jak binarne, jak scalanie) to te „dobre" — płytkie i skalowalne; łańcuchowe (silnia, suma) — te, które lepiej iterować.

🔍 Sprawdź, czy umiesz

• Napisać dowolną prostą rekurencję, nazywając bazę i krok, zanim ją zapiszesz.
• Prześledzić rekurencję rysunkiem stosu — schodzenie i wracanie.
• Wskazać dwa śmiertelne błędy (brak bazy, krok bez zmniejszania) i ich objaw.

---