Rekurencja Wyjaśniona: Kiedy ją Stosować, a Kiedy Nie

Funkcja, która wywołuje sama siebie, ma maksymalną głębokość, i jest ona mniejsza niż większość się spodziewa: 1000 wywołań w CPython domyślnie, w okolicach 10 000-15 000 w Node i silnikach przeglądarek, zależnie od tego, jak dużo zajmuje każda ramka. Przekroczenie tego limitu nie zwalnia programu. Program się wysypuje. Python zgłasza RecursionError: maximum recursion depth exceeded; JavaScript zgłasza RangeError: Maximum call stack size exceeded.

Oba błędy mają tę samą przyczynę, a gdy już ją zobaczysz, będziesz wiedzieć, kiedy rekurencja jest właściwym narzędziem, a kiedy staje się ryzykiem.

Co rekurencyjna funkcja robi ze stosem wywołań

Każde wywołanie funkcji kładzie ramkę na stosie: argumenty, zmienne lokalne, adres powrotu. Zwykłe wywołanie wraca, a jego ramka zostaje zdjęta ze stosu. Wywołanie rekurencyjne nie może jeszcze wrócić, bo czeka na wywołanie, które właśnie zrobiło, więc każda ramka zostaje na stosie, dopóki nie skończy się ta pod nią.

1
2
3
4

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(4) buduje cztery ramki na stosie, zanim którakolwiek z nich zwróci wartość:

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # przypadek bazowy, stos przestaje rosnąć

Tylko gdy factorial(1) zwraca 1, stos zaczyna się rozwijać: 2 * 1, potem 3 * 2, potem 4 * 6, wynik 24.

Dwa elementy sprawiają, że to działa. Przypadek bazowy (n <= 1) zatrzymuje rekurencję. Przypadek rekurencyjny wywołuje funkcję ponownie z danymi, które przybliżają się do przypadku bazowego. Usuń jeden z nich, a funkcja nigdy nie przestanie wywoływać samej siebie: w Pythonie dojdziesz do RecursionError w mniej niż tysiąc wywołań, w języku bez limitu proces padnie przez przepełnienie stosu.

Kiedy rekurencja jest właściwym narzędziem: dane zagnieżdżone

Rekurencja zarabia na swoje miejsce, gdy dane są zagnieżdżone na głębokość, której nie znasz wcześniej: drzewo, system plików, dowolnie zagnieżdżony JSON. Pętla po takich danych potrzebuje stosu, który musisz prowadzić ręcznie. Rekurencja daje go za darmo, bo stos wywołań jest tym stosem, który był potrzebny.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Każde wywołanie flatten obsługuje jeden poziom. Gdy trafi na zagnieżdżoną listę, przekazuje ją nowemu wywołaniu, a stos pamięta, gdzie wrócić w zewnętrznej liście, kiedy wewnętrzna się skończy. Wersja iteracyjna musiałaby śledzić tę pozycję samodzielnie.

Przechodzenie po drzewie katalogów ma tę samą strukturę:

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

total_size nie obchodzi, czy katalog ma jeden poziom głębokości, czy dziesięć. Każde wywołanie obsługuje własny path.

Kiedy rekurencja jest złym narzędziem: płaskie, długie dane wejściowe

Sumowanie płaskiej listy to odwrotny przypadek. Nie ma tu żadnego zagnieżdżenia, więc rekurencja nie daje nic, poza ryzykiem dla stosu.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

Działa na małych danych i pada na realnych:

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Dwa tysiące elementów, jedna ramka na element, dwa razy więcej niż domyślny limit. Wersja z pętlą używa jednej ramki niezależnie od długości listy:

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) zwraca wynik natychmiast. W ujęciu notacji Big O obie wersje są O(n) czasowo, ale rekurencyjna kosztuje dodatkowo O(n) pamięci stosu, a ta pamięć jest ograniczona do około tysiąca ramek.

Czy tail-call optimization rozwiązuje problem głębokiej rekurencji w Pythonie lub JavaScript?

Nie. W sum_recursive ostatnią rzeczą, która się dzieje, jest dodawanie, nie wywołanie rekurencyjne, więc każda ramka musi żyć, żeby odebrać wynik i go dodać. Można przepisać funkcję tak, by wywołanie rekurencyjne było ostatnią operacją, przekazując bieżącą sumę jako argument:

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

W języku z tail-call optimization kompilator widzi, że po wywołaniu nic już nie potrzebuje ramki wywołującego, i używa jej ponownie, zamiast odkładać nową. Rekurencja zamienia się pod spodem w pętlę.

CPython tego nie robi, z rozmysłu: główni deweloperzy odrzucili tę funkcję, bo utrudniłaby odczytywanie tracebacków. sum_tail wciąż trafia na limit przy liście 2000 elementów. Specyfikacja ES2015 JavaScript przewiduje proper tail calls, ale V8 (Chrome, Node.js) i SpiderMonkey (Firefox) nigdy ich nie wdrożyły; robi to tylko JavaScriptCore, silnik Safari.

Reguła jest więc taka sama w obu językach. Jeśli rozmiar danych wejściowych decyduje o głębokości rekurencji, nie licz na to, że silnik cię uratuje. Zamień ją na pętlę albo ogranicz głębokość.

Jak memoization naprawia wolną rekurencję

Niektóre funkcje rekurencyjne nigdy nie zbliżają się do limitu głębokości. Ich problemem jest to, że liczą to samo wielokrotnie. Naiwny rekurencyjny Fibonacci to klasyczny przykład:

1
2
3
4

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

fib(5) wywołuje fib(4) i fib(3), a fib(4) wywołuje fib(3) jeszcze raz. To powielanie kumuluje się na każdym poziomie, więc liczba wywołań rośnie wykładniczo z n (o czynnik około 1,6 na krok, zwykle zapisywany jako górna granica O(2^n)). W CPython fib(30) zajmuje już około jednej dziesiątej sekundy, a fib(40) ponad dziesięć sekund.

Rozwiązanie zostawia rekurencję bez zmian i buforuje wyniki, więc każde różne dane wejściowe są liczone tylko raz:

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

lru_cache to dekorator. Owija fib_memo, i kiedy argument się powtarza, zwraca zapisany wynik, zamiast ponownie wykonywać ciało funkcji. fib_memo(40) zwraca wynik natychmiast.

Głębokość się nie zmienia: fib_memo(40) wciąż potrzebuje około 40 ramek stosu. Zmienia się liczba wywołań, która spada z wykładniczej do liniowej. Płacisz O(n) pamięci za cache i zyskujesz O(n) czasu, a nie wykładniczy.

Rekurencja czy iteracja: co wybrać

Jeden przypadek zasługuje na więcej niż wiersz tabeli. Jeśli głębokość rekurencji jest kontrolowana przez dane wejściowe, którym nie ufasz, to wektor ataku typu denial-of-service. Rekurencyjny parser, który schodzi o jeden poziom głębiej na każdy zagnieżdżony nawias kwadratowy w tekście od użytkownika, może wysypać każdy, kto wyśle kilka tysięcy znaków [. Ogranicz głębokość jawnie albo nie używaj rekurencji.

Jak zamienić funkcję rekurencyjną na pętlę

Bezpośrednim zamiennikiem rekurencji po drzewie jest jawny stos: list, na której sam robisz push i pop, prowadzona przez pętlę while. Oto flatten przepisana w ten sposób:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

Daje ten sam wynik z jedną ramką stosu, niezależnie od tego, jak głębokie są dane wejściowe. Kosztem jest zarządzanie, które widać na pierwszy rzut oka: stos iteratorów to dokładnie to, co wcześniej śledził za ciebie stos wywołań.

Gdy następnym razem napiszesz funkcję rekurencyjną, zapytaj, jak głęboko może sięgnąć. Jeśli odpowiedź jest mała i znana (plik konfiguracyjny, drzewo komponentów UI, drzewo parsowania dla twojej własnej gramatyki), zostaw rekurencję. Jeśli odpowiedź to “tyle, ile powiedzą dane wejściowe”, napisz pętlę.

Powiązane artykuły

• Notacja Big O Wyjaśniona na Przykładach Kodu
• Git Bisect: Jak Znaleźć Commit, który Wprowadził Buga