Rekurencja i iteracja to dwa sposoby opisania tego samego procesu obliczeniowego. Wybór między nimi pojawia się w niemal każdej rozmowie technicznej z algorytmów, bo dotyka modelu wykonania, kosztu pamięci i czytelności kodu.
W tym artykule zestawiam oba podejścia z perspektywy kandydata: kiedy która wersja jest naturalna, jakie pułapki czekają w Pythonie i jak czytać kompromisy między nimi. Implementacje pokazuję w Pythonie dla zwięzłości — wzorzec jest language-agnostic, analogicznie zachowa się w Javie, Ruby czy JavaScript.
Skupiam się na poziomie intuicji, nie na asymptotyce. Big O pojawia się tylko tam, gdzie istotnie zmienia decyzję — pełna lekcja notacji jest osobnym tematem.
Czym jest rekurencja, czym iteracja
Rekurencja rozwiązuje problem przez wywołanie tej samej funkcji dla mniejszego przypadku. Iteracja powtarza kroki w pętli, zwykle aktualizując stan lokalny. Obie techniki mogą opisać ten sam proces.
W rozmowie rekrutacyjnej ważne jest wskazanie przypadku bazowego dla rekurencji oraz warunku zakończenia pętli dla iteracji. Brak jednego z nich zwykle oznacza nieskończone wywołania albo nieskończoną pętlę.
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n):
result = 1
for value in range(2, n + 1):
result *= value
return result
print(factorial_recursive(5)) # expected_output: 120
print(factorial_iterative(5)) # expected_output: 120
Stos wywołań i sys.getrecursionlimit()
Każde wywołanie rekurencyjne w Pythonie tworzy nową ramkę na stosie wywołań. Ramka przechowuje lokalne zmienne, argumenty i miejsce powrotu, dlatego głęboka rekurencja zużywa pamięć niezależnie od prostoty funkcji.
sys.getrecursionlimit() pokazuje limit głębokości rekurencji ustawiony dla interpretera. Dokumentacja Pythona opisuje go jako zabezpieczenie przed przepełnieniem stosu C, a nie jako obietnicę, że głęboka rekurencja jest dobrym stylem.
import sys
def depth_left(n):
if n == 0:
return "done"
return depth_left(n - 1)
limit = sys.getrecursionlimit()
print(type(limit).__name__) # expected_output: int
print(limit >= 100) # expected_output: True
print(depth_left(3)) # expected_output: done
Tail call optimization — Python jej nie robi
Tail call występuje, gdy ostatnią operacją funkcji jest wywołanie innej funkcji. Tail call optimization usuwa wtedy potrzebę zachowania bieżącej ramki, ale Python celowo tego nie implementuje.
Guido van Rossum w tekście „Tail Recursion Elimination” z 2009 roku napisał: „I don't want TRE in the language”. Uzasadniał to między innymi czytelnymi tracebackami i przewidywalną semantyką.
def countdown_tail(n, acc):
if n == 0:
return acc
return countdown_tail(n - 1, acc + 1)
def countdown_loop(n):
acc = 0
while n:
n -= 1
acc += 1
return acc
print(countdown_tail(5, 0)) # expected_output: 5
print(countdown_loop(5)) # expected_output: 5
Silnia: rekurencyjnie vs iteracyjnie
Silnia jest dobrym przykładem dydaktycznym, bo definicja matematyczna ma naturalny przypadek bazowy. Dziedzina to nieujemne liczby całkowite: dla n <= 1 wynik to 1, a dla większych wartości funkcja redukuje problem do n - 1.
W praktycznym Pythonie wersja iteracyjna jest zwykle prostsza operacyjnie. Nie zużywa dodatkowych ramek stosu, łatwiej obsługuje duże n i nie wymaga myślenia o limicie rekurencji.
def recursive_factorial(n):
if n <= 1:
return 1
return n * recursive_factorial(n - 1)
print(recursive_factorial(6)) # expected_output: 720
def iterative_factorial(n):
result = 1
for value in range(2, n + 1):
result *= value
return result
print(iterative_factorial(6)) # expected_output: 720
Fibonacci naive: powtarzane podproblemy
Naiwna rekurencja dla Fibonacciego pokazuje koszt powtarzania tych samych podproblemów dla nieujemnych n. fib(5) woła fib(4) i fib(3), a fib(4) znowu woła fib(3) oraz fib(2).
Drzewo wywołań szybko się rozrasta: wiele gałęzi liczy identyczne wartości od zera. Czas pracy jest wykładniczy, często upraszczany do O(2^n), choć precyzyjnie rośnie jak Θ(φ^n).
def fibonacci_naive(n):
if n < 2:
return n
return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
print(fibonacci_naive(6)) # expected_output: 8
print(fibonacci_naive(7)) # expected_output: 13
Fibonacci iteracyjnie: dwa ostatnie wyniki
Iteracyjny Fibonacci dla nieujemnych n trzyma tylko dwa ostatnie wyniki. Przypisanie a, b = b, a + b przesuwa okno obliczeń bez tworzenia drzewa wywołań i bez dodatkowych ramek stosu — czas O(n), pamięć pomocnicza O(1) licząc liczbę zmiennych stanu.
To jest standardowy kontrast rekrutacyjny: ten sam wynik, inny model wykonania. Iteracja jest tu naturalna, bo problem jest liniowym przejściem przez kolejne indeksy, a nie eksploracją struktury drzewa.
def fibonacci_iterative(n):
a = 0
b = 1
for _ in range(n):
a, b = b, a + b
return a
print(fibonacci_iterative(6)) # expected_output: 8
print(fibonacci_iterative(7)) # expected_output: 13
Memoization: cache usuwa powtórzenia
Memoization zapisuje wyniki dla argumentów, które już policzono. W Pythonie @functools.lru_cache dodaje taką pamięć podręczną do funkcji, dzięki czemu powtórne wywołanie z tym samym n zwraca gotowy wynik.
Dla Fibonacciego oznacza to, że fib(8) nie przelicza wielokrotnie fib(6), fib(5) i mniejszych wartości. Nadal używa rekurencji, ale usuwa główny problem powtarzanych poddrzew.
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_cached(n):
if n < 2:
return n
return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)
print(fibonacci_cached(8)) # expected_output: 21
print(fibonacci_cached.cache_info().hits > 0) # expected_output: True
Suma listy: rekurencja vs iteracja vs sum()
Sumowanie listy nie ma naturalnej struktury drzewa; to liniowe przejście po elementach. Rekurencja tworzy jedną ramkę stosu na każdy krok, więc przy domyślnym limicie CPythona (~1000) lista 10^4 elementów zwykle zakończy się RecursionError na długo przed końcem.
Wersja w przykładzie używa numbers[1:], co dodatkowo kopiuje suffix listy w każdym wywołaniu — pamięć rośnie kwadratowo. Iteracja i wbudowane sum() nie używają ani stosu wywołań, ani kopii sufiksu.
def sum_recursive(numbers):
if not numbers:
return 0
return numbers[0] + sum_recursive(numbers[1:])
def sum_iterative(numbers):
total = 0
for number in numbers:
total += number
return total
values = [1, 2, 3, 4]
print(sum_recursive(values)) # expected_output: 10
print(sum_iterative(values)) # expected_output: 10
print(sum(values)) # expected_output: 10
Konwersja rekurencji na iterację z explicit stack
Rekurencyjne DFS korzysta z ukrytego stosu wywołań. Iteracyjna wersja robi to samo jawnie: przechowuje w liście węzły czekające na odwiedzenie i sama decyduje o kolejności dodawania dzieci.
Ten wzorzec jest ważny przy drzewach, grafach i parserach. Zamiast zwiększać limit rekurencji, można przenieść kontrolę pamięci do struktury danych, którą łatwiej mierzyć i testować.
tree = ("A", ("B", None, None), ("C", None, None))
def dfs_iterative(root):
stack = [root]
seen = []
while stack:
node = stack.pop()
if node is None:
continue
value, left, right = node
seen.append(value)
stack.extend([right, left])
return seen
print(dfs_iterative(tree)) # expected_output: ['A', 'B', 'C']
Kiedy rekurencja naturalna: drzewa, divide-and-conquer
Rekurencja jest naturalna, gdy dane same są rekurencyjne: drzewo ma korzeń i poddrzewa, katalog ma podkatalogi, wyrażenie ma podwyrażenia. Kod często staje się wtedy bezpośrednim opisem struktury problemu.
Divide-and-conquer także pasuje do rekurencji: dzielisz problem, rozwiązujesz części, łączysz wyniki. Merge sort jest klasycznym przykładem, ale tutaj wystarczy rozumieć wzorzec, nie sortowanie jako osobny temat.
def count_nodes(node):
if node is None:
return 0
value, left, right = node
return 1 + count_nodes(left) + count_nodes(right)
tree = ("root", ("left", None, None), ("right", None, None))
print(count_nodes(tree)) # expected_output: 3
Kiedy iteracja naturalna: hot loops, duże n, brak drzewa
Iteracja jest naturalna dla liczników, strumieni, tablic, kolejek i pętli wykonywanych bardzo często. Gdy nie ma hierarchii ani podproblemów, pętla zwykle pokazuje zamiar bez kosztu ramek stosu.
Dla dużego n iteracja daje przewidywalne zużycie pamięci i łatwiej współpracuje z przerwaniem, logowaniem oraz batchowaniem. W kodzie biznesowym to często ważniejsze niż akademicka zwięzłość funkcji rekurencyjnej.
def count_matches(numbers, target):
matches = 0
for number in numbers:
if number == target:
matches += 1
return matches
values = [2, 1, 2, 3, 2]
print(count_matches(values, 2)) # expected_output: 3
Mutual recursion
Mutual recursion zachodzi, gdy funkcje wywołują się nawzajem. Dla nieujemnych liczb całkowitych is_even() może delegować do is_odd(), a is_odd() z powrotem do is_even(), aż liczba dojdzie do przypadku bazowego.
Ten wzorzec bywa przydatny w parserach i automatach stanów, ale w Pythonie nadal zużywa stos. Tail call optimization nie uratuje tu głębokich wejść, nawet jeśli wywołanie wygląda jak ostatnia operacja.
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
print(is_even(4)) # expected_output: True
print(is_odd(4)) # expected_output: False
Sygnały rozpoznawcze: kiedy rekurencja, kiedy iteracja
Rozpoznanie wzorca jest na rozmowie ważniejsze niż sama implementacja. Sygnał → wybór:
"struktura ma korzeń i poddrzewa" → rekurencja (drzewo, AST, parser)
(drzewo, hierarchia, JSON)
"podziel problem na dwie części, → rekurencja (divide-and-conquer)
połącz wyniki" (merge sort, quick)
"podproblemy nakładają się" → rekurencja + memoization (lru_cache)
(Fibonacci, edit distance)
"liniowe przejście / strumień / → iteracja (pętla, for/while)
hot loop / duże n"
"mutual recursion" → rekurencja (parser, automat)
(is_even/is_odd, parser states)
"limit głębokości > 1000" → iteracja z explicit stack
(deep tree, deep recursion)
Sygnał odwrotny — kiedy rekurencja jest pułapką: hot loop wykonywany tysiące razy na sekundę (koszt ramek bije narzut pętli), płaska tablica bez hierarchii (pętla pokazuje zamiar prościej), bardzo głębokie drzewa (sys.getrecursionlimit() blokuje).
Najczęstsze błędy
Brak przypadku bazowego. Funkcja rekurencyjna bez if base_case: return ... woła samą siebie w nieskończoność, aż RecursionError. Mechanizm: każde wywołanie powiększa call stack, brak warunku stopu = stos pęka. Naprawa: zawsze zacznij implementację od if not data: return ... przed właściwą logiką.
Tail-recursive zapis ≠ optymalizacja w Pythonie. Python nie robi TCO — zapis tail-recursive nadal tworzy nową ramkę stosu per wywołanie. Mechanizm błędu: kandydat ze Scheme/Haskell przenosi wzorzec, oczekuje O(1) pamięci stosu. Naprawa: dla głębokich rekurencji w Pythonie konwertuj na iterację z explicit stack.
Naive Fibonacci jako wzorzec rekurencji. fib(n-1) + fib(n-2) jest wykładniczy O(2^n), nie z powodu samej rekurencji, ale powtarzających się podproblemów. Mechanizm: drzewo wywołań ma duplikaty. Naprawa: dodaj @functools.lru_cache — sprowadza do O(n) przez memoization powtórzeń.
numbers[1:] w rekurencji na liście. Slicing tworzy nową listę przy każdym wywołaniu — pamięć rośnie kwadratowo zamiast liniowo. Mechanizm błędu: dla n=1000 zamiast O(n) pamięci masz O(n²). Naprawa: użyj indeksu zamiast slice — recurse(values, index + 1).
Rekurencja w hot loop. Funkcja rekurencyjna wywoływana 10⁶ razy na sekundę traci na samym narzucie call stack vs for. Mechanizm: każde wywołanie to alokacja ramki, push/pop, return overhead. Naprawa: dla hot path zawsze sprawdź czy iteracja nie wystarczy, nawet jeśli rekurencja jest „elegantniejsza".
FAQ
Czy rekurencja jest zawsze wolniejsza od iteracji?
Niekoniecznie. Asymptotycznie obie mają tę samą złożoność dla tego samego algorytmu. Różnica leży w stałych: rekurencja w Pythonie tworzy ramki stosu na każde wywołanie, więc dla dużego n iteracja zwykle wygrywa praktycznie. Naiwny Fibonacci jest wykładniczy nie z powodu rekurencji, ale powtarzanych podproblemów — @lru_cache przywraca go do O(n).
Dlaczego Python nie wspiera tail call optimization?
Guido van Rossum w 2009 roku wyjaśnił, że TRE komplikuje traceback i niszczy debugowalność. CPython celowo zachowuje wszystkie ramki, więc każde rekurencyjne wywołanie zużywa pamięć stosu — niezależnie od tego, czy jest na pozycji tail call.
Jaki jest domyślny limit rekurencji w Pythonie?
W typowym CPythonie sys.getrecursionlimit() zwraca 1000. Można to zmienić przez sys.setrecursionlimit(), ale jest to zabezpieczenie przed przepełnieniem stosu C interpretera. Lista 10^4 elementów rekurencyjnie zsumowana zwykle przerwie się RecursionError znacznie wcześniej.
Kiedy używać @functools.lru_cache?
Gdy funkcja jest deterministyczna (te same argumenty → ten sam wynik), argumenty są hashable, a powtarzające się wywołania są kosztowne. Klasyczny przypadek to memoization w rekurencji z nakładającymi się podproblemami. Nie używaj lru_cache na funkcjach z efektami ubocznymi ani z mutowalnymi argumentami.
Czy każdą rekurencję można zamienić na iterację?
Tak — explicit stack zawsze załatwia sprawę. DFS na drzewie to klasyczny przykład: zastępujesz wywołania rekurencyjne jawną listą węzłów do odwiedzenia. Iteracyjny zapis bywa mniej czytelny, ale daje pełną kontrolę nad pamięcią i nie podlega limitowi rekurencji.
Czym różni się rekurencja od mutual recursion?
W zwykłej rekurencji funkcja wywołuje samą siebie. Mutual recursion zachodzi, gdy dwie (lub więcej) funkcje wywołują się nawzajem — np. is_even woła is_odd, a is_odd woła is_even. Dla Pythona koszt jest taki sam: każde przejście między funkcjami też tworzy ramkę stosu.
Powiązane tematy
- Drzewa Binarne — Wzorzec Rekurencyjny — drzewa to klasyczny use case rekurencji; tam są pre/in/post-order traversale i decyzja DFS rekurencyjny vs iteracyjny.
- Stos i Kolejka — LIFO i FIFO — call stack rekurencji to ukryty stack LIFO; explicit stack jako iteracyjne równoważnik.
- Big O w 10 Minut — Notacja Złożoności — kontekst dla
O(2^n)naive Fibonacci,O(n)po memoization,O(n)call stack overhead.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący stos wywołań, tail call, memoization i wybór między rekurencją a iteracją: https://odpytywarka.pl/q/rEbsph.
Masz własne notatki na rozmowę kwalifikacyjną? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Python docs —
sys.setrecursionlimit— oficjalna dokumentacja interpretera Pythona o limicie rekurencji. - Python docs —
functools.lru_cache— dekorator do memoization. - Guido van Rossum — „Tail Recursion Elimination” (2009) — uzasadnienie braku TCO w Pythonie.
- Wikipedia — Recursion (computer science) — definicje i klasyfikacja rekurencji.