Ciągi: iteracyjnie i rekurencyjnie

🎯 Po co Ci to?

Rok 1202. Leonardo z Pizy, zwany Fibonaccim, zadaje w podręczniku rachunków zadanie o rozmnażających się królikach — i mimochodem zapisuje ciąg, który od ośmiu wieków nie chce zejść ze sceny: 1, 1, 2, 3, 5, 8, 13, 21… Znajdziesz go w spiralach słoneczników i muszli, w analizie giełdowej i — co dla nas najważniejsze — w co drugim zadaniu maturalnym o ciągach. Dziś policzysz go na dwa fundamentalnie różne sposoby. Jeden jest szybki. Drugi jest piękny. A napięcie między nimi to jeden z głównych wątków całej informatyki.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • rozróżnić wzór ogólny ciągu od definicji rekurencyjnej (wyraz z poprzednich wyrazów);
  • policzyć wyraz ciągu iteracyjnie — pętlą przesuwającą „okno" ostatnich wartości;
  • policzyć go rekurencyjnie wprost z definicji — i porównać oba podejścia.

📘 Wyjaśnienie

Ciąg można zadać na dwa sposoby. Wzorem ogólnym — przepisem na $n$-ty wyraz wprost: $a_n = 2n + 1$ (nieparzyste: 3, 5, 7…). Policzenie $a_{1000}$ to jedno podstawienie. Ale wielu ciągów nie da się (łatwo) tak zapisać — za to łatwo powiedzieć, jak powstaje kolejny wyraz z poprzednich:

📐 DEFINICJA — definicja rekurencyjna ciągu: określenie ciągu przez (1) wyrazy początkowe oraz (2) regułę, jak każdy następny wyraz wyliczyć z wcześniejszych.

Po ludzku: nie mówię ci, ile wynosi setny wyraz — mówię, jak z dwóch ostatnich zrobić następny, i od czego zacząć. Czym NIE jest: definicją bez dna. Wyrazy początkowe to fundament — bez nich reguła „następny = suma dwóch poprzednich" wisiałaby w próżni.

Ciąg Fibonacciego to definicja rekurencyjna w najczystszej postaci:

$$F_1 = 1, \quad F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \ \text{dla } n > 2$$

Sposób 1: iteracyjnie. Buduj ciąg od dołu, pamiętając tylko dwa ostatnie wyrazy (więcej nie potrzeba — reguła dalej nie sięga):

def fib_iter(n):
    if n <= 2:
        return 1
    a, b = 1, 1                # okno: dwa ostatnie wyrazy
    for _ in range(n - 2):     # tyle razy przesuń okno
        a, b = b, a + b
    return b

Podmiana a, b = b, a + b to serce algorytmu: stare b staje się nowym a, a nowa wartość to suma okna. (Nazwa _ dla licznika to konwencja: „ta zmienna jest mi niepotrzebna, liczy się sama liczba obrotów".) Koszt: $n$ obrotów — $F_{1000}$ w mgnieniu oka.

Sposób 2: rekurencyjnie. Definicja matematyczna jest przepisem — więc przepiszmy ją dosłownie:

def fib_rek(n):
    if n <= 2:
        return 1               # wyrazy początkowe = przypadki bazowe
    return fib_rek(n - 1) + fib_rek(n - 2)

Cztery linijki, uroda absolutna: kod jest definicją. Sprawdź: fib_rek(6) policzy fib_rek(5) + fib_rek(4), te rozpadną się dalej, aż wszystko oprze się o jedynki — wynik 8. Poprawnie.

💭 Pomyśl: Wywołaj w myślach fib_rek(6) i policz, ile razy w całej kaskadzie zostanie wywołane fib_rek(3). Podpowiedź: narysuj drzewko wywołań.

Sprawdź odpowiedź

fib_rek(6) woła (5) i (4); (5) woła (4) i (3); każde (4) woła (3) i (2)… fib_rek(3) policzy się trzy razy — za każdym razem od zera, z identycznym wynikiem. Dla fib_rek(30) te powtórki eksplodują: łącznie ponad milion wywołań, żeby policzyć trzydziesty wyraz, który iteracja ma w 30 obrotów. A fib_rek(60) nie skończy się za Twojego życia. Drzewo wywołań podwaja się na każdym poziomie — koszt rośnie wykładniczo (poznajesz drugą stronę monety z 2.7?).

Werdykt? Nie „rekurencja jest zła". Rekurencja dosłownie przepisana z definicji bywa rozrzutna, bo liczy to samo wielokrotnie — u Euklidesa (4.2) każda podproblem był inny i rekurencja śmigała; u Fibonacciego podproblemy się powtarzają i rekurencja się krztusi. Iteracja z oknem to jedno lekarstwo. Drugie — zapamiętywanie już policzonych wyników — dostanie własną jednostkę (8.3), a rehabilitacja rekurencji nastąpi w dziale 7. Na razie masz najważniejsze: dwa poprawne algorytmy mogą dzielić przepaść kosztów, i to Ty wybierasz.

🧮 Prześledź

Prześledź fib_iter(7) — uzupełnij okno po każdym obrocie:

obrót a b
start 1 1
1 ? ?
2 ? ?
3 ? ?
4 ? ?
5 ? ?
Sprawdź odpowiedź

(1,1) → (1,2) → (2,3) → (3,5) → (5,8) → (8,13). Zwrócone b = 13 = $F_7$. ✓ Okno przesuwa się po ciągu jak lupa po linijce: w każdej chwili widzisz tylko dwa wyrazy, ale to wystarcza, bo reguła nie sięga głębiej. Gdyby reguła sięgała trzy wyrazy wstecz — okno miałoby trzy zmienne.

⚠️ Uwaga, pułapka

W definicji rekurencyjnej najłatwiej zepsuć przypadki bazowe. Zapomnisz warunku n <= 2 — funkcja będzie wołać fib_rek(0), fib_rek(-1), fib_rek(-2)… bez końca, aż Python przerwie program komunikatem o przekroczeniu głębokości rekurencji (to rekurencyjny odpowiednik pętli nieskończonej z 3.3). Reguła żelazna: najpierw pisz przypadki bazowe, potem regułę — fundament przed piętrami.

🤯 Ciekawostka

Iloraz sąsiednich wyrazów Fibonacciego — $\frac{13}{8} = 1{,}625$, $\frac{21}{13} \approx 1{,}615$, $\frac{34}{21} \approx 1{,}619$ — zbiega do złotej liczby $\varphi \approx 1{,}618$, proporcji znanej z architektury i malarstwa. Dlatego prostokąty o bokach z sąsiednich wyrazów Fibonacciego wyglądają „szlachetnie", a spirale słonecznika układają się w 34 i 55 rzędów. Osiemsetletnie zadanie o królikach okazało się przepisem na estetykę.

🛠️ Teraz Ty

Ciąg „potrójny": $T_1 = T_2 = T_3 = 1$, dalej $T_n = T_{n-1} + T_{n-2} + T_{n-3}$. Napisz wersję iteracyjną (okno trzech zmiennych!) i rekurencyjną; policz $T_{10}$ obiema (musi wyjść to samo) i sprawdź, przy jakim $n$ wersja rekurencyjna zaczyna zauważalnie mulić. Bez komputera: wypisz ręcznie $T_1 \dots T_8$.

📐 Definicje tej lekcji

  • Definicja rekurencyjna ciągu — wyrazy początkowe + reguła „następny z poprzednich".
  • Metoda iteracyjna — pętla przesuwająca okno ostatnich wyrazów; koszt liniowy.
  • Metoda rekurencyjna — funkcja przepisująca definicję; elegancka, ale przy powtarzających się podproblemach wykładniczo droga.

📌 Najważniejsze w pigułce

  • Fibonacci: $F_n = F_{n-1} + F_{n-2}$, start od dwóch jedynek — wzorcowa definicja rekurencyjna.
  • Iteracja z oknem dwóch zmiennych liczy $F_n$ w $n$ krokach; naiwna rekurencja — w wykładniczo wielu, bo powtarza podproblemy.
  • Przypadki bazowe pisz najpierw; bez nich rekurencja spada bez dna.

🎒 Zadania

  1. Dla ciągu $a_1 = 3$, $a_n = 2 a_{n-1} - 1$: wypisz ręcznie $a_2 \dots a_5$, napisz a_iter(n) i policz $a_{20}$. Rozpoznajesz wzór ogólny?
Wskazówka i odpowiedź

5, 9, 17, 33 — każdy wyraz to podwojenie poprzedniego minus 1. Okno wystarczy jednowyrazowe: x = 3, w pętli x = 2*x - 1. $a_{20} = 2^{20} + 1 = 1,048,577$ (wzór ogólny $a_n = 2^{n-1} + 1$ — sprawdź indukcyjnie na pierwszych wyrazach). Morał: szerokość okna = głębokość reguły; nie każdy ciąg potrzebuje dwóch zmiennych.

  1. Ile wywołań wykona fib_rek(6)? Policz dokładnie, rysując drzewo (albo dodając do funkcji licznik).
Wskazówka i odpowiedź

Wywołania: (6),(5),(4)×2,(3)×3,(2)×5,(1)×3 — razem 15. Ciekawostka w ciekawostce: liczba wywołań fib_rek(n) to $2F_n - 1$ (dla $n=6$: $2 \cdot 8 - 1 = 15$) — koszt naiwnej rekurencji sam jest ciągiem Fibonacciego. Problem opisuje własną cenę.

  1. Bank nalicza co miesiąc 1% odsetek i klient dopłaca 100 zł. Zapisz saldo jako ciąg rekurencyjny ($S_0 = 1000$), policz iteracyjnie $S_{12}$ i wyjaśnij, czemu tu wersja rekurencyjna nie byłaby katastrofą.
Wskazówka i odpowiedź

$S_n = 1{,}01 \cdot S_{n-1} + 100$; pętla dwunastu obrotów daje $S_{12} \approx 2395{,}08$ zł. Rekurencja byłaby tu niegroźna: każde wywołanie robi jedno wywołanie ($S_{n}$ zależy tylko od $S_{n-1}$) — łańcuszek, nie drzewo, więc koszt liniowy jak iteracji. Eksplozja Fibonacciego brała się z rozgałęzienia (dwa wywołania na poziom); pojedyncza zależność jest bezpieczna. Ucz się patrzeć na kształt drzewa wywołań, nie na samo słowo „rekurencja".

🔍 Sprawdź, czy umiesz

  • Podać z pamięci definicję rekurencyjną Fibonacciego i osiem pierwszych wyrazów.
  • Napisać wersję iteracyjną dowolnego ciągu „wyraz z dwóch poprzednich".
  • Wyjaśnić na drzewie wywołań, skąd bierze się wykładniczy koszt naiwnej rekurencji.

Ucz się tej jednostki z asystentem