Fibonacci w Pythonie - Rekurencja, optymalizacja i pułapki

Rekurencyjny zapis Fibonacciego to jeden z najlepszych przykładów na to, jak działa myślenie algorytmiczne w Pythonie. Pokażę tu nie tylko samą definicję i kod, ale też to, kiedy takie rozwiązanie ma sens, dlaczego bywa wolne i jak je poprawić bez psucia prostoty. Dzięki temu łatwiej zrozumiesz zarówno samą rekurencję, jak i typowe pułapki, które pojawiają się przy pierwszych ćwiczeniach z programowania.

Na czym polega rekurencyjny zapis ciągu Fibonacciego

Najpierw trzeba rozdzielić dwie rzeczy: sam ciąg i sposób jego zapisu. Ciąg Fibonacciego definiuje się rekurencyjnie, czyli każdy kolejny element wynika z dwóch poprzednich. W najczęściej spotykanej wersji przyjmuje się, że F(0) = 0, F(1) = 1, a potem dla każdego `n > 1` zachodzi zależność `F(n) = F(n-1) + F(n-2)`.

To właśnie dlatego Fibonacci tak dobrze nadaje się do nauki rekurencji. Masz tu bardzo prostą regułę, ale jednocześnie od razu widać koszt uboczny takiego podejścia: ta sama wartość może być liczona wiele razy. Dla początkującego to świetny materiał szkoleniowy, bo pokazuje nie tylko ideę, ale też konsekwencje projektu algorytmu.

W praktyce spotkasz też inną konwencję startową, w której pierwsze dwa wyrazy mają wartość `1`, czyli `1, 1, 2, 3, 5...`. To nie jest błąd, tylko inny zapis numeracji. Dla kodu ważniejsze od samej tradycji jest to, żeby konsekwentnie trzymać jedną definicję w całym programie. Skoro definicja jest już jasna, czas przejść do najprostszego kodu w Pythonie.

Jak napisać prostą funkcję w Pythonie

Ja zwykle zaczynam od wersji, która jest możliwie krótka i czytelna. Taki kod najlepiej pokazuje ideę, nawet jeśli nie jest jeszcze optymalny pod względem wydajności.

def fib(n):
    if n < 0:
        raise ValueError("n musi być >= 0")
    if n in (0, 1):
        return n
    return fib(n - 1) + fib(n - 2)

Ta funkcja ma trzy ważne elementy. Pierwszy to kontrola poprawności danych wejściowych, bo liczby ujemne nie pasują do klasycznego ciągu Fibonacciego. Drugi to warunek stopu, czyli moment, w którym funkcja przestaje wywoływać samą siebie. Trzeci to właściwy krok rekurencyjny, gdzie wynik zależy od dwóch mniejszych wywołań.

Jeśli wywołasz `fib(5)`, program rozbije zadanie na `fib(4)` i `fib(3)`, potem każdy z tych wyników rozbije się dalej. To dobrze pokazuje, jak działa rekurencja, ale też ujawnia problem powtórzeń. Właśnie dlatego warto spojrzeć na to drzewo wywołań trochę krytycznie, a nie tylko zachwycać się elegancją zapisu.

• `fib(0)` zwraca `0` bez dalszych wywołań.
• `fib(1)` zwraca `1` bez dalszych wywołań.
• `fib(2)` wywołuje `fib(1)` i `fib(0)`.
• `fib(5)` wielokrotnie potrzebuje tych samych wyników, na przykład `fib(3)` i `fib(2)`.

To prowadzi bezpośrednio do pytania, które zwykle pojawia się jako następne: skoro kod jest taki prosty, dlaczego przy większych danych działa coraz wolniej? Odpowiedź jest mniej intuicyjna, ale bardzo ważna.

Dlaczego naiwna rekurencja szybko zwalnia

Problem nie leży w samej rekurencji, tylko w jej naiwnym użyciu. W powyższej wersji ta sama wartość jest obliczana wiele razy, więc liczba wywołań rośnie lawinowo. Dla małych `n` tego prawie nie widać, ale przy większych wejściach różnica robi się ogromna.

W praktyce złożoność czasowa takiego rozwiązania to około O(2^n), czyli bardzo szybko robi się kosztowne obliczeniowo. Pamięć też nie jest darmowa, bo każde wywołanie trafia na stos wywołań funkcji. Dla porządku zestawiam najważniejsze warianty w prostej tabeli.

Ten kontrast jest ważny, bo wielu początkujących zakłada, że skoro kod jest krótki, to będzie też szybki. W programowaniu to założenie często zawodzi. Następny krok to pokazanie, jak zachować prostotę rekurencji, ale usunąć największy koszt obliczeń.

Jak ograniczyć koszt obliczeń

Najprostsza poprawka to memoizacja, czyli zapisywanie wcześniej policzonych wyników. Dzięki temu funkcja nie liczy tego samego drugi raz, tylko korzysta z pamięci podręcznej. W Pythonie bardzo wygodnie robi się to dekoratorem `lru_cache`.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
    if n < 0:
        raise ValueError("n musi być >= 0")
    if n in (0, 1):
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

To rozwiązanie zachowuje czytelność rekurencji, ale usuwa główny problem: powtarzanie tych samych obliczeń. W praktyce często wystarcza, jeśli chcesz zrozumieć ideę i jednocześnie nie czekać wieczności na wynik większego `n`.

Jeżeli jednak zależy Ci na maksymalnej prostocie wykonania, pętla nadal będzie rozsądniejsza niż rekurencja. W zadaniach produkcyjnych zwykle wybieram wersję iteracyjną, bo jest przewidywalna, oszczędna i nie ryzykuje przeciążenia stosu wywołań. To dobry moment, żeby nazwać typowe błędy, które widzę najczęściej u osób uczących się tego tematu.

Najczęstsze błędy przy implementacji

• Brak warunku stopu - funkcja wywołuje samą siebie bez końca i kończy się błędem rekurencji.
• Zła numeracja początkowa - ktoś miesza wersję `0, 1` z wersją `1, 1` i dostaje przesunięte wyniki.
• Za duże `n` bez optymalizacji - naiwna wersja robi się bardzo wolna już przy relatywnie niewielkich wartościach.
• Ignorowanie limitu stosu - w Pythonie głęboka rekurencja może zakończyć się `RecursionError`.
• Brak walidacji wejścia - wartości ujemne albo niecałkowite powinny być odrzucone albo obsłużone świadomie.

Ja szczególnie zwracam uwagę na warunek stopu, bo to najczęstsze miejsce, w którym logika zaczyna się rozjeżdżać. Jeśli fundament jest ustawiony źle, reszta kodu może wyglądać poprawnie, a i tak nie zadziała. Skoro błędy są już nazwane, pozostaje pytanie praktyczne: kiedy rekurencja naprawdę ma sens, a kiedy to po prostu zbyt drogi wybór?

Kiedy rekurencja ma sens, a kiedy lepiej wybrać pętlę

W nauce rekurencja ma ogromny sens, bo pomaga zrozumieć warunki końcowe, dzielenie problemu na mniejsze części i działanie stosu wywołań. Właśnie dlatego Fibonacci tak często pojawia się na początku kursów Pythona. To nie jest przypadek, tylko dobrze dobrany przykład dydaktyczny.

W praktyce sytuacja wygląda inaczej. Gdy liczę pojedynczy wyraz dla małego `n`, rekurencja jest w pełni akceptowalna, zwłaszcza jeśli kod ma być krótki i czytelny. Gdy jednak potrzebuję wielu wartości albo większego zakresu, wybieram pętlę lub memoizację, bo to daje lepszy kompromis między prostotą a wydajnością.

Jeśli miałbym wskazać jedną regułę, powiedziałbym tak: rekurencja jest świetna do zrozumienia problemu, ale nie zawsze jest najlepsza do jego szybkiego rozwiązania. To rozróżnienie naprawdę pomaga, kiedy przechodzisz z ćwiczeń do pisania normalnego kodu.

Co ten przykład uczy poza samym Fibonacciem

W tym jednym zadaniu kryje się więcej niż tylko słynny ciąg. Uczysz się tu trzech rzeczy, które wracają w programowaniu bez przerwy: definiowania warunku stopu, rozbijania problemu na mniejsze części i oceniania kosztu obliczeń. To właśnie dlatego Fibonacci jest tak popularny w materiałach dla początkujących.

• Najpierw sprawdzam, czy problem ma naturalny punkt zakończenia.
• Potem pytam, czy podproblemy się powtarzają.
• Na końcu oceniam, czy czytelność kodu nie odbywa się kosztem zbyt dużej ceny wykonania.

Jeśli opanujesz ten schemat na przykładzie Fibonacciego, dużo łatwiej będzie Ci zrozumieć inne klasyczne zadania rekurencyjne, takie jak silnia, przeszukiwanie drzewa czy dzielenie zbioru na mniejsze fragmenty. I to właśnie jest najważniejsza korzyść z tego ćwiczenia: nie chodzi o sam ciąg, tylko o sposób myślenia, który zostaje na dłużej.