Rekurencja to technika, w której funkcja wywołuje samą siebie, żeby rozłożyć duży problem na mniejsze egzemplarze tego samego problemu. Każde wywołanie zajmuje się odrobinę prostszą wersją zadania, aż dotrze do przypadku tak banalnego, że odpowiedź znasz od ręki, bez kolejnego wywołania. Ten najprostszy przypadek nazywa się warunkiem zatrzymania (ang. base case) i bez niego cała konstrukcja zamienia się w nieskończoną pętlę, która zaraz wywali ci program.
Działa to tak: funkcja sprawdza, czy trafiła już na przypadek bazowy. Jeśli tak — zwraca gotowy wynik. Jeśli nie — woła samą siebie z mniejszym argumentem (krok rekurencyjny) i składa wynik z tego, co dostanie z powrotem. Kluczowe słowo to „mniejszym”: każde wywołanie musi przybliżać cię do warunku zatrzymania, inaczej nigdy go nie osiągniesz.
Rekurencja świetnie pasuje do problemów, które same w sobie mają strukturę zagnieżdżoną: przechodzenie po drzewach (DOM, system plików), sortowanie typu quicksort czy mergesort, parsowanie JSON-a, algorytmy typu „dziel i zwyciężaj”. Tam, gdzie dane mają kształt drzewa albo dzielą się na podproblemy, kod rekurencyjny bywa krótszy i czytelniejszy niż pętle.
Przykład z praktyki
Klasyk to silnia. W Pythonie:
def silnia(n):
if n <= 1: return 1 # warunek zatrzymania
return n * silnia(n - 1) # krok rekurencyjny
Bardziej życiowy scenariusz: chcesz policzyć rozmiar katalogu razem z podkatalogami. Z linii komend zrobi to za ciebie rekurencyjnie du -sh ./projekt albo find . -type f — oba schodzą w głąb drzewa folderów bez pytania cię, ile poziomów jest do końca.
Na co uważać
- Brak warunku zatrzymania albo argument, który nie maleje — dostaniesz
RecursionError(Python) lubStackOverflowError(Java/JVM). Każde wywołanie odkłada ramkę na stosie, a stos jest skończony. - Domyślny limit: w Pythonie to zwykle 1000 zagnieżdżeń (
sys.getrecursionlimit()). Przy głębokich strukturach pętla bywa bezpieczniejsza. - Mit "rekurencja zawsze elegancka" — naiwne liczenie Fibonacciego rekurencyjnie ma złożoność wykładniczą, bo liczy te same wartości w kółko. Ratunek: memoizacja albo wersja iteracyjna.
Niektóre języki optymalizują tzw. tail call (wywołanie rekurencyjne jako ostatnia operacja), ale Python tego nie robi — nie licz na to.
Pojęcia powiązane: warunek zatrzymania (base case), stos wywołań (call stack), memoizacja, dziel i zwyciężaj, iteracja, drzewo, przepełnienie stosu.