Podręcznik

4. Rekurencja

Rekurencja to technika programistyczna i koncepcja matematyczna, w której funkcja wywołuje samą siebie w celu rozwiązania mniejszej części tego samego problemu. Jest to bardzo potężne narzędzie, które pozwala w elegancki sposób rozwiązywać złożone zadania poprzez ich sprowadzanie do prostszych przypadków. W kodzie możemy zaprezentować rekurencję w następujący sposób:

void funkcja_rekrencyjna(){
	...
  funkcja_rekrencyjna();
  ...
}

W implementacji funkcja wywołuje samą siebie. Najważniejszą rzeczą do zapamiętania w przypadku rekurencji jest konieczność odpowiedniego zdefiniowania warunku końca. W przypadku gdy warunek zostanie w nieprawidłowy sposób zdefiniowany może to prowadzić do nieskończonego wywoływania funkcji. Jednym z najprostszych przykładów wykorzystania rekurencji jest wyznaczenie wartości silni.

int silnia(int n) {
    if (n == 0 || n == 1) {
        return 1; // silnia z 0 i 1 to 1
    } else {
        return n * silnia(n - 1); // rekurencyjne wywołanie
    }
}

Możliwe jest także iteracyjne wyznaczenie wartości silni.

int silnia(int n) {
    int wynik = 1;

    for (int i = 2; i <= n; ++i) {
        wynik *= i;
    }

    return wynik;
}

Porównując różne sposoby obliczania silni w języku C++, można zauważyć istotne różnice między podejściem rekurencyjnym a iteracyjnym. Rekurencja odwołuje się do eleganckiego, matematycznego sposobu myślenia o problemie – funkcja wywołuje samą siebie, aż do osiągnięcia warunku brzegowego. Jest to sposób bardziej naturalny z punktu widzenia teorii algorytmów i często łatwiejszy do napisania w kilku linijkach kodu.

Z kolei iteracja opiera się na konstrukcjach pętli, takich jak for czy while, i działa w sposób bardziej techniczny. Zajmuje mniej pamięci, ponieważ nie wymaga dodatkowego miejsca na stosie wywołań funkcji, co ma znaczenie przy dużych wartościach n. Dzięki temu iteracyjne podejście jest zwykle wydajniejsze i bezpieczniejsze w środowiskach o ograniczonych zasobach.

Główne zalety rekurencji wynikają z jej elegancji, przejrzystości i bezpośredniego odwzorowania logicznej struktury wielu problemów. Poniżej przedstawiam kluczowe korzyści płynące z jej stosowania.

Przede wszystkim rekurencja pozwala na bardzo zwięzłe i czytelne wyrażenie algorytmów, które mają charakter powtarzalny lub dzielą problem na mniejsze podproblemy. Problemy takie jak silnia, ciąg Fibonacciego, przeszukiwanie struktur drzewiastych (np. drzewa binarnego), rozwiązywanie zadań typu "dziel i zwyciężaj" (np. sortowanie szybkiego podziału – quicksort) dają się naturalnie wyrazić właśnie rekurencyjnie.

Drugą zaletą rekurencji jest to, że wiele złożonych struktur danych (takich jak drzewa, grafy, listy zagnieżdżone) można przetwarzać w sposób bardzo intuicyjny – odwiedzając je w głąb (DFS – depth-first search) bez konieczności ręcznego stosowania struktur pomocniczych, takich jak stos czy kolejka.

Rekurencja bywa też niezastąpiona w algorytmach, które wymagają eksploracji wielu wariantów rozwiązania, np. w problemach kombinatorycznych, algorytmach typu backtracking (jak rozwiązywanie sudoku, znajdowanie ścieżek w labiryncie) czy generowaniu permutacji i podzbiorów.