Rekurencja (Rekursja)

Mechanizm działania rekurencji

Rekurencja (Recursion) to technika polegająca na redukcji złożonego problemu do mniejszych instancji tego samego problemu. Każde wywołanie rekurencyjne odkłada ramkę stosu (stack frame) ze swoimi zmiennymi lokalnymi na stosie wywołań (Call Stack).

Dwa obowiązkowe elementy funkcji rekurencyjnej:

1. Warunek bazowy (Warunek stopu / Base Case): Trywialny przypadek, dla którego funkcja zwraca wynik bezpośrednio bez kolejnych wywołań rekurencyjnych (zapobiega nieskończonej pętli).
2. Krok rekurencyjny (Recursive Step): Wywołanie funkcji z argumentem zbliżającym się do warunku bazowego.

// Przykład: Obliczanie silni n! rekurencyjnie
public static int Silnia(int n) {
    if (n <= 1) return 1;          // WARUNEK STOPU
    return n * Silnia(n - 1);       // KROK REKURENCYJNY
}

Wady i zalety rekurencji:

• Zalety: Bardzo zwięzły, elegancki i czytelny kod przy przetwarzaniu struktur nieliniowych (drzewa, grafy, algorytmy typu Dziel i Zwyciężaj).
• Wady: Narzut pamięciowy i czasowy na odkładanie ramek na stosie. Zbyt głęboka rekurencja prowadzi do błędu StackOverflowError.

Pułapki na egzaminie INF.04:

• Brak poprawnego warunku stopu w funkcji rekurencyjnej powoduje przepełnienie stosu wywołań (Stack Overflow).