Rekurencja w programowaniu

Jak działa rekurencja?

Funkcja rekurencyjna to taka, która w swoim ciele zawiera wywołanie samej siebie. Aby rekurencja nie spowodowała przepełnienia stosu wywołań (Stack Overflow), bezwzględnie musi posiadać warunek stopu (warunek bazowy).

// Przykład obliczania silni (n!):
function silnia(n) {
    // 1. Warunek stopu (baza rekurencji):
    if (n <= 1) return 1;
    // 2. Krok rekurencyjny:
    return n * silnia(n - 1);
}

console.log(silnia(5)); // Wynik: 120

Zalety i wady rekurencji:

• Zalety: Zwięzły i czytelny kod dla problemów o strukturze rekurencyjnej (np. przeglądanie drzewa DOM, przeszukiwanie katalogów, algorytmy dziel i zwyciężaj).
• Wady: Zużywa pamięć na stosie dla każdej ramki wywołania; w przypadku braku warunku stopu zawiesza aplikację.

Najczęstsze pułapki na egzaminie INF.03:

• Zadania egzaminacyjne często proszą o podanie wyniku działania krótkiej funkcji rekurencyjnej dla podanego argumentu wejściowego (np. potęgowanie, ciąg Fibonacciego, NWD).