Algorytmy rekurencyjne

Rekurencja pojawia się bardzo wcześnie podczas nauki programowania, ale zwykle dopiero przy większych problemach widać, po co naprawdę istnieje. W prostych zadaniach często da się ją zastąpić pętlą, jednak przy strukturach drzewiastych, analizie grafów, parsowaniu składni albo algorytmach dziel i zwyciężaj kod iteracyjny szybko staje się trudny do utrzymania. W praktyce największy problem nie polega na samym zapisaniu funkcji rekurencyjnej, tylko na zrozumieniu przepływu wywołań, pamięci stosu oraz kosztu czasowego. Właśnie dlatego algorytmy rekurencyjne są jednocześnie bardzo eleganckie i bardzo niebezpieczne, jeśli programista nie kontroluje ich głębokości oraz liczby wywołań.

Spis Treści

Algorytmy rekurencyjne i mechanizm działania funkcji wywołującej samą siebie krok po kroku

Rekurencja polega na tym, że funkcja wywołuje samą siebie, ale dla prostszego przypadku niż aktualny. Program dochodzi w ten sposób do problemu elementarnego, który można rozwiązać bez kolejnych wywołań. Ten najprostszy przypadek nazywa się warunkiem stopu.

Bez warunku stopu funkcja będzie wywoływać samą siebie w nieskończoność, aż do przepełnienia stosu. To jeden z najczęstszych błędów początkujących.

Każde wywołanie funkcji tworzy nową ramkę stosu. Ramka zawiera:

argumenty funkcji,
zmienne lokalne,
adres powrotu,
stan wykonania.

Jeżeli funkcja wywoła samą siebie 1000 razy, na stosie znajdzie się 1000 ramek. W językach takich jak C czy C++ bardzo głęboka rekurencja może zakończyć program błędem segmentation fault albo stack overflow.

Przykład matematyczny bardzo dobrze pokazuje ideę działania. Silnia liczby n definiowana jest jako: $n! = n \cdot (n-1)!$

oraz: $0! = 1$

To naturalna definicja rekurencyjna.

Przykład	Kod
C	`c\n#include <stdio.h>\n\nint silnia(int n)\n{\n if(n == 0)\n return 1;\n\n return n * silnia(n - 1);\n}\n\nint main()\n{\n printf(\"%d\\n\", silnia(5));\n return 0;\n}\n`
C++	`cpp\n#include <iostream>\nusing namespace std;\n\nint silnia(int n)\n{\n if(n == 0)\n return 1;\n\n return n * silnia(n - 1);\n}\n\nint main()\n{\n cout << silnia(5) << endl;\n return 0;\n}\n`
Python	`python\ndef silnia(n):\n if n == 0:\n return 1\n\n return n * silnia(n - 1)\n\nprint(silnia(5))\n`

Przepływ wykonania dla silnia(5) wygląda tak:

silnia(5) czeka na wynik silnia(4)
silnia(4) czeka na wynik silnia(3)
silnia(3) czeka na wynik silnia(2)
silnia(2) czeka na wynik silnia(1)
silnia(1) czeka na wynik silnia(0)
silnia(0) zwraca 1
następuje rozwijanie stosu:
- 1 * 1
- 2 * 1
- 3 * 2
- 4 * 6
- 5 * 24

W praktyce bardzo ważne jest rozróżnienie dwóch etapów:

schodzenia w dół rekurencji,
powrotu wyników.

Wiele błędów logicznych bierze się z niezrozumienia, że kod po wywołaniu rekurencyjnym wykona się dopiero podczas wychodzenia ze stosu.

Dlaczego algorytmy rekurencyjne są naturalne dla drzew, grafów i problemów dzielonych na mniejsze części

Rekurencja najlepiej działa tam, gdzie struktura danych sama ma charakter rekurencyjny. Drzewo binarne jest klasycznym przykładem.

Każdy węzeł drzewa:

posiada wartość,
posiada lewe poddrzewo,
posiada prawe poddrzewo.

Każde poddrzewo jest znowu drzewem. To idealnie pasuje do rekurencji.

Przechodzenie drzewa preorder:

odwiedź korzeń,
przejdź lewe poddrzewo,
przejdź prawe poddrzewo.

Przykład	Kod
C	`c\n#include <stdio.h>\n#include <stdlib.h>\n\nstruct Node\n{\n int value;\n struct Node* left;\n struct Node* right;\n};\n\nvoid preorder(struct Node* root)\n{\n if(root == NULL)\n return;\n\n printf(\"%d \", root->value);\n\n preorder(root->left);\n preorder(root->right);\n}\n`
C++	`cpp\n#include <iostream>\nusing namespace std;\n\nstruct Node\n{\n int value;\n Node* left;\n Node* right;\n};\n\nvoid preorder(Node* root)\n{\n if(root == nullptr)\n return;\n\n cout << root->value << \" \";\n\n preorder(root->left);\n preorder(root->right);\n}\n`
Python	`python\nclass Node:\n def __init__(self, value):\n self.value = value\n self.left = None\n self.right = None\n\n\ndef preorder(root):\n if root is None:\n return\n\n print(root.value)\n\n preorder(root.left)\n preorder(root.right)\n`

Przy drzewach iteracyjna wersja często wymaga własnego stosu. Rekurencja używa stosu funkcji procesora, więc kod pozostaje krótszy.

Podobnie działa DFS w grafach.

Język	Kod
Python	`python\ngraf = {\n 1: [2, 3],\n 2: [4],\n 3: [],\n 4: []\n}\n\nodwiedzone = set()\n\n\ndef dfs(v):\n if v in odwiedzone:\n return\n\n odwiedzone.add(v)\n print(v)\n\n for sasiad in graf[v]:\n dfs(sasiad)\n\n\ndfs(1)\n`

Tutaj bardzo łatwo popełnić błąd polegający na braku tablicy odwiedzonych wierzchołków. W grafie zawierającym cykl program może wejść w nieskończoną rekurencję.

W praktycznych systemach takie błędy kończą się:

zawieszeniem procesu,
zużyciem pamięci,
restartem usługi,
utratą stabilności aplikacji.

Zależność między złożonością czasową a liczbą wywołań funkcji w rekurencji

Największy problem wielu algorytmów rekurencyjnych nie wynika z samej rekurencji, ale z liczby powtarzanych obliczeń.

Klasyczny przykład to ciąg Fibonacciego.

Definicja: $F(n) = F(n-1) + F(n-2)$ F(n)=F(n−1)+F(n−2)

Język	Kod
C	`c\n#include <stdio.h>\n\nint fib(int n)\n{\n if(n <= 1)\n return n;\n\n return fib(n - 1) + fib(n - 2);\n}\n`
Python	`python\ndef fib(n):\n if n <= 1:\n return n\n\n return fib(n - 1) + fib(n - 2)\n`

Dla fib(40) liczba wywołań jest ogromna.

Przybliżona złożoność: $O(2^n)$ Powód:

fib(40) liczy fib(39) i fib(38),
fib(39) ponownie liczy fib(38),
te same wyniki są obliczane wielokrotnie.

Drzewo wywołań rośnie wykładniczo.

Tutaj pojawia się memoizacja.

Memoizacja polega na zapamiętywaniu wcześniej obliczonych wyników.

Język	Kod
Python	`python\ncache = {}\n\n\ndef fib(n):\n if n in cache:\n return cache[n]\n\n if n <= 1:\n return n\n\n wynik = fib(n - 1) + fib(n - 2)\n cache[n] = wynik\n\n return wynik\n`

Po zastosowaniu memoizacji złożoność spada do: $O(n)$ O(n)

Różnica jest gigantyczna:

wersja klasyczna dla dużych n może działać kilka sekund,
wersja z memoizacją wykonuje się praktycznie natychmiast.

W systemach produkcyjnych niewłaściwa rekurencja często prowadzi do:

przeciążenia CPU,
lawinowego wzrostu czasu odpowiedzi,
błędów timeout,
zbyt dużego zużycia pamięci.

Rekurencja ogonowa i wpływ optymalizacji stosu na wydajność programu

Rekurencja ogonowa występuje wtedy, gdy ostatnią operacją funkcji jest wywołanie samej siebie.

Przykład:

Język	Kod
C	`c\n#include <stdio.h>\n\nint suma(int n, int acc)\n{\n if(n == 0)\n return acc;\n\n return suma(n - 1, acc + n);\n}\n`
Python	`python\ndef suma(n, acc):\n if n == 0:\n return acc\n\n return suma(n - 1, acc + n)\n`

W niektórych kompilatorach możliwa jest optymalizacja tail recursion:

zamiast tworzyć nową ramkę stosu,
funkcja nadpisuje bieżącą.

To redukuje zużycie pamięci.

Problem praktyczny:

Python nie implementuje optymalizacji tail recursion,
C i C++ mogą ją stosować zależnie od kompilatora i flag optymalizacji,
Java zwykle nie gwarantuje takiej optymalizacji.

Dlatego kod poprawny teoretycznie może nadal przepełnić stos.

Przykładowe limity:

Python domyślnie około 1000 wywołań,
JVM zwykle kilka tysięcy,
C/C++ zależnie od systemu i rozmiaru stosu procesu.

W praktyce bardzo głęboka rekurencja bywa zastępowana:

własnym stosem,
iteracją,
BFS zamiast DFS,
dynamicznym programowaniem.

Algorytmy rekurencyjne w sortowaniu, podziale problemu i przetwarzaniu dużych zbiorów danych

Najważniejsze praktyczne algorytmy rekurencyjne zwykle korzystają z techniki dziel i zwyciężaj.

Schemat:

podziel problem,
rozwiąż mniejsze podproblemy,
połącz wyniki.

Merge sort jest klasycznym przykładem.

Złożoność: $O(n \log n)$ O(nlogn)

Język Kod

Python python\ndef merge_sort(tab):\n if len(tab) <= 1:\n return tab\n\n mid = len(tab) // 2\n\n lewa = merge_sort(tab[:mid])\n prawa = merge_sort(tab[mid:])\n\n wynik = []\n\n i = 0\n j = 0\n\n while i < len(lewa) and j < len(prawa):\n if lewa[i] < prawa[j]:\n wynik.append(lewa[i])\n i += 1\n else:\n wynik.append(prawa[j])\n j += 1\n\n wynik.extend(lewa[i:])\n wynik.extend(prawa[j:])\n\n return wynik\n

Język	Kod
Python	`python\ndef merge_sort(tab):\n if len(tab) <= 1:\n return tab\n\n mid = len(tab) // 2\n\n lewa = merge_sort(tab[:mid])\n prawa = merge_sort(tab[mid:])\n\n wynik = []\n\n i = 0\n j = 0\n\n while i < len(lewa) and j < len(prawa):\n if lewa[i] < prawa[j]:\n wynik.append(lewa[i])\n i += 1\n else:\n wynik.append(prawa[j])\n j += 1\n\n wynik.extend(lewa[i:])\n wynik.extend(prawa[j:])\n\n return wynik\n`

Quick sort również wykorzystuje rekurencję.

Średnia złożoność: $O(n \log n)$ O(nlogn)

Najgorszy przypadek: $O(n^2)$ O(n2)

Największy praktyczny problem quicksorta to zły wybór pivota.

Dla już posortowanych danych klasyczna implementacja może:

wykonywać ogromną liczbę porównań,
tworzyć bardzo głęboką rekurencję,
powodować przepełnienie stosu.

Dlatego profesjonalne implementacje używają:

mediany trzech elementów,
introsort,
hybrydowych metod sortowania.

Rekurencja występuje także w:

parserach składni,
kompilatorach,
analizie XML,
systemach plików,
silnikach szachowych,
przeszukiwaniu przestrzeni stanów,
algorytmach AI,
generowaniu kombinacji i permutacji.

Przykład generowania permutacji:

Język	Kod
Python	`python\ndef permutacje(tab, poczatek=0):\n if poczatek == len(tab):\n print(tab)\n return\n\n for i in range(poczatek, len(tab)):\n tab[poczatek], tab[i] = tab[i], tab[poczatek]\n\n permutacje(tab, poczatek + 1)\n\n tab[poczatek], tab[i] = tab[i], tab[poczatek]\n\n\npermutacje([1, 2, 3])\n`

Tutaj liczba możliwych wyników wynosi: $n!$ Dla:

3 elementów → 6 permutacji,
10 elementów → 3 628 800,
15 elementów → ponad bilion.

To pokazuje, że nawet poprawny algorytm rekurencyjny może być praktycznie niewykonalny dla większych danych.

Najczęstsze błędy spotykane podczas implementacji funkcji rekurencyjnych i sposoby ich wykrywania

Najczęstszy problem to brak poprawnego warunku stopu.

Przykład błędny:

Język	Kod
Python	`python\ndef blad(n):\n return blad(n - 1)\n`

Taki kod kończy się:

RecursionError w Pythonie,
stack overflow w C/C++,
awarią procesu.

Drugi częsty błąd:

zły kierunek zmiany argumentu.

Jeżeli wartość nie zbliża się do warunku stopu, rekurencja nigdy się nie kończy.

Trzeci problem:

nadmiar kopiowania danych.

Przekazywanie dużych struktur przez wartość może dramatycznie spowolnić program.

W C++ lepiej stosować referencje:

Język	Kod
C++	`cpp\nvoid funkcja(const vector<int>& dane)\n{\n}\n`

Kolejny problem:

mieszanie logiki zejścia i powrotu.

Wiele osób nie rozumie, dlaczego:

print(n)
rek(n - 1)
print(n)

drukuje liczby dwa razy w różnych momentach.

To efekt rozwijania stosu.

Praktyczna metoda debugowania:

wypisywanie poziomu rekurencji,
wizualizacja drzewa wywołań,
ręczne śledzenie stosu,
analiza liczby wywołań funkcji.

Dobrym ćwiczeniem jest rozpisanie każdej ramki funkcji na kartce. Przy bardziej złożonych algorytmach często oszczędza to godziny debugowania.

Kiedy rekurencja jest lepsza od iteracji, a kiedy prowadzi do problemów wydajnościowych

Rekurencja daje bardzo czytelny kod dla:

drzew,
DFS,
divide and conquer,
backtrackingu,
parserów.

Iteracja zwykle wygrywa przy:

prostych pętlach,
dużej głębokości danych,
systemach embedded,
krytycznej optymalizacji pamięci,
zadaniach liniowych.

Porównanie praktyczne:

Cecha	Rekurencja	Iteracja
Czytelność	często bardzo wysoka	zależy od problemu
Zużycie pamięci	większe	mniejsze
Ryzyko stack overflow	wysokie	niskie
Łatwość dla drzew	bardzo dobra	średnia
Kontrola wykonania	trudniejsza	łatwiejsza
Wydajność	czasem niższa	zwykle stabilniejsza

W praktyce doświadczeni programiści nie traktują rekurencji jako „lepszego” rozwiązania. To po prostu narzędzie.

Czasami rekurencyjny DFS jest idealny i daje kod krótszy o połowę. Innym razem ten sam mechanizm potrafi zabić wydajność aplikacji przy większych danych wejściowych.

Dobry programista zwykle analizuje:

maksymalną głębokość,
złożoność czasową,
zużycie pamięci,
możliwość memoizacji,
ryzyko powtórnych obliczeń,
rozmiar danych wejściowych.

Rekurencja jest bardzo elegancka matematycznie, ale komputer wykonuje ją fizycznie przez stos wywołań i pamięć operacyjną. To ograniczenie zawsze trzeba brać pod uwagę podczas projektowania algorytmów.

FAQ

Czy rekurencję da się zawsze zastąpić iteracją?

Teoretycznie tak. Każdy algorytm rekurencyjny można przepisać iteracyjnie, zwykle przy użyciu własnego stosu. Problem polega na tym, że kod bywa wtedy dużo trudniejszy do utrzymania.

Dlaczego Python ma niski limit rekurencji?

Python celowo ogranicza głębokość wywołań, aby zmniejszyć ryzyko przepełnienia stosu i zawieszania interpretera. Domyślny limit wynosi zwykle około 1000 wywołań.

Czy rekurencja jest wolniejsza od pętli?

Najczęściej tak, ponieważ każde wywołanie funkcji generuje dodatkowy koszt:

tworzenie ramki stosu,
przekazywanie argumentów,
powrót z funkcji.

Przy małych danych różnica może być niewielka.

Gdzie rekurencja jest używana najczęściej?

Najczęściej w:

drzewach,
grafach,
parserach,
algorytmach dziel i zwyciężaj,
backtrackingu,
dynamicznym programowaniu,
kompilatorach.

Dlaczego Fibonacci jest złym przykładem rekurencji?

Klasyczna implementacja wykonuje ogromną liczbę powtarzających się obliczeń. To dobry przykład edukacyjny, ale słabe rozwiązanie praktyczne bez memoizacji.

Co oznacza stack overflow?

To sytuacja, w której stos wywołań funkcji przekracza dostępny rozmiar pamięci. Najczęściej powodem jest:

nieskończona rekurencja,
bardzo głębokie wywołania,
zbyt duże zmienne lokalne.

Czy rekurencja ogonowa zawsze jest optymalizowana?

Nie. Zależy to od:

języka,
kompilatora,
ustawień optymalizacji,
sposobu napisania funkcji.

Python nie wykonuje takiej optymalizacji.

Źródło Foto: Freepik