Rekurencja: co to jest i jak działa na przykładach

Co to jest rekurencja

Rekurencja (z łac. recurrere, „przybiec z powrotem”) oznacza odwoływanie się funkcji lub definicji do samej siebie. W programowaniu rekurencyjna jest funkcja, która w swoim ciele wywołuje samą siebie z innymi (zwykle mniejszymi) argumentami. Tę samą ideę da się zapisać jako definicję matematyczną, jak w przypadku silni czy ciągu Fibonacciego.

Rekurencyjne rozwiązanie składa się z dwóch części:

1. Warunek stopu (przypadek bazowy): najprostszy przypadek, którego wynik znasz od razu.
2. Krok rekurencyjny: sprowadzenie zadania do mniejszego zadania tego samego rodzaju i użycie jego wyniku.

Bez przypadku bazowego definicja nigdy się nie kończy. W programie kończy się to błędem przekroczenia głębokości rekurencji, o czym jest niżej.

Silnia: najprostsza funkcja rekurencyjna

Silnia liczby naturalnej n to iloczyn wszystkich dodatnich liczb naturalnych nie większych niż n, a dodatkowo przyjmuje się, że 0! = 1. Definicja rekurencyjna ma dwa przypadki: 0! = 1 oraz n! = n · (n − 1)! dla n ≥ 1.

Zapis w Pythonie:

def silnia(n):
    if n == 0:          # warunek stopu
        return 1
    return n * silnia(n - 1)   # krok rekurencyjny

print(silnia(5))   # 120

Kod uruchomiony w Pythonie 3.13: silnia(5) daje 120, a silnia(10) daje 3628800.

Stos wywołań dla silnia(3)

Każde wywołanie czeka na wynik następnego, dopóki nie zostanie osiągnięty warunek stopu. Wywołania odkładane są na stosie, a wyniki wracają w odwrotnej kolejności:

Wynik: 3! = 6. W kroku 4 na stosie są jednocześnie cztery wywołania; głębokość rośnie o 1 przy każdym zmniejszeniu n.

Ciąg Fibonacciego

Ciąg Fibonacciego jest zdefiniowany rekurencyjnie: pierwszy wyraz jest równy 0, drugi 1, a każdy następny jest sumą dwóch poprzednich. Zapis: F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2) dla n > 1. Pierwsze wyrazy to 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

def fib(n):
    if n < 2:           # dwa warunki stopu: F(0) = 0 i F(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))   # 55

Tu każde wywołanie rodzi dwa kolejne, więc powstaje drzewo wywołań, a nie pojedynczy łańcuch.

Koszt: dlaczego fib(30) jest wolne

To samo podzadanie liczone jest wielokrotnie: fib(5) wywołuje fib(4) i fib(3), a fib(4) znowu wywołuje fib(3). Liczba wszystkich wywołań (zmierzona w Pythonie 3.13 licznikiem w funkcji) rośnie bardzo szybko:

Dla n = 30 funkcja wykonuje ponad 2,6 miliona wywołań, żeby dać wynik, który pętla policzy w 30 krokach.

Wersja z pamięcią (memoizacja)

Zapamiętanie już policzonych wyników (memoizacja) usuwa powtórzenia. W Pythonie robi to dekorator functools.cache, który według dokumentacji tworzy lekką, nieograniczoną pamięć podręczną wyników funkcji.

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(30))   # 832040
print(fib(90))   # 2880067194370816120

W teście z licznikiem fib(30) z pamięcią wykonało ciało funkcji tylko 31 razy (po jednym dla każdego n od 0 do 30) zamiast ponad 2,6 miliona. Dokumentacja Pythona pokazuje ten sam pomysł w przykładzie z lru_cache(maxsize=None) jako technikę programowania dynamicznego.

Stos wywołań i limit rekurencji w Pythonie

Każde wywołanie funkcji zajmuje miejsce na stosie, więc zbyt głęboka rekurencja kończy się błędem. Python ma limit głębokości: według dokumentacji sys.getrecursionlimit() zwraca maksymalną głębokość stosu interpretera, a limit ten zapobiega przepełnieniu stosu języka C i awarii Pythona. Gdy limit zostaje przekroczony, interpreter zgłasza wyjątek RecursionError.

W Pythonie 3.13.15 sprawdzony limit wynosi 1000 (wartość domyślna może zależeć od wersji i środowiska). Wywołanie silnia(5000) kończy się błędem RecursionError: maximum recursion depth exceeded, tak samo jak funkcja bez warunku stopu.

Limit można zmienić przez sys.setrecursionlimit(limit), ale dokumentacja ostrzega, że najwyższy możliwy limit zależy od platformy i trzeba to robić ostrożnie, bo zbyt wysoki limit może spowodować awarię programu. Dla głębokich zadań lepsze jest rozwiązanie iteracyjne.

Rekurencja a iteracja

Iteracja to powtarzanie kroków w pętli. Zadanie rozwiązane rekurencyjnie można zwykle zapisać także pętlą. Silnia i Fibonacci w wersji iteracyjnej:

def silnia_it(n):
    wynik = 1
    for k in range(2, n + 1):
        wynik *= k
    return wynik

def fib_it(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(silnia_it(5))   # 120
print(fib_it(30))     # 832040
print(fib_it(90))     # 2880067194370816120

Wyniki zgadzają się z wersjami rekurencyjnymi. Porównanie:

Wybierz rekurencję, gdy zadanie z natury dzieli się na mniejsze zadania tego samego typu, a głębokość jest niewielka. Gdy liczba kroków jest duża albo wersja rekurencyjna powtarza obliczenia, użyj pętli lub memoizacji.

Zobacz też: Algorytm, Algorytm Euklidesa, Sortowanie bąbelkowe.