Rekurencja: Incepcja w Programowaniu

Wyobraź sobie, że stoisz między dwoma lustrami – widzisz swoje odbicie, w którym jest odbicie, w którym jest kolejne odbicie. W informatyce, gdy funkcja (program) wywołuje we własnym wnętrzu samą siebie, nazywamy to Rekurencją.

To jeden z ulubionych i najtrudniejszych tematów na Maturze z Informatyki. CKE uwielbia pytać: "Oto krótki kod, ile razy wywoła się funkcja dla n=4?".

1. Złota zasada Rekurencji: Warunek Zakończenia (Klamra)

Pętla while bez zwiększania licznika zawiesi komputer. Podobnie rekurencja bez Warunku Zatrzymania (Warunku Brzegowego) będzie wywoływać się w nieskończoność, aż zapełni całą dostępną pamięć operacyjną (RAM) dla programu. Ten tragiczny moment to błąd znany w całej branży IT jako Stack Overflow (Przepełnienie Stosu).

Każda funkcja rekurencyjna na maturze wygląda w 99% tak:

int silnia(int n) {
    // 1. Warunek Brzegowy (Nasza klamra hamująca!)
    if (n == 0) {
        return 1;
    }
    
    // 2. Krok rekurencyjny (Lustro)
    return n * silnia(n - 1);
}

2. Rysowanie Drzewa Wywołań (Łopatologicznie)

Jeśli na maturze masz kod z rekurencją, NIGDY nie licz tego w głowie. Zawsze rysuj drzewo na brudnopisie.

Jak działa silnia(3)?

1. Komputer wchodzi do silnia(3). Czy 3 == 0? Nie. Omija if.
2. Dochodzi do return 3 * silnia(2). KOMPUTER ZAMRAŻA TĄ LINIJKĘ! Nie zna wyniku silnia(2), więc nie może pomnożyć. Zawiesza stan silnia(3) w pamięci.
3. Wchodzi głębiej do silnia(2). Czy 2 == 0? Nie.
4. Dochodzi do return 2 * silnia(1). Znowu zamraża!
5. Wchodzi do silnia(1). Zwraca return 1 * silnia(0). Zamraża!
6. Wchodzi do silnia(0). O! Tutaj if (n == 0) odpala się jako prawda. Funkcja nie wywołuje już samej siebie. Zwraca czystą, pewną liczbę: 1.

Teraz następuje zjawisko Zwijania Stosu (odbudowywania):

• silnia(1) pyta: hej, masz wynik? Tak, to 1. Zatem 1 * 1 = 1.
• silnia(2) odblokowuje się: 2 * 1 = 2.
• silnia(3) (nasz startowy problem) wreszcie dostaje wynik: 3 * 2 = 6. Gotowe!

3. Ciąg Fibonacciego (Podwójne Lustro) 🪤

Najgorszy przypadek dla ucznia to tzw. Podwójna Rekurencja.

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    return fib(n-1) + fib(n-2); // Podwójne wywołanie!
}

Gdy narysujesz drzewo dla fib(4), zobaczysz, że rozgałęzia się ono na boki gigantycznie szybko! Co gorsza, fib(2) jest w tym drzewie liczone wielokrotnie od zera za każdym razem. To jest maturalny klasyk: Pytanie, dlaczego ten kod działa wolno dla n=50? Odpowiedź: Ponieważ powtarza obliczenia dla tych samych wartości wielokrotnie (złożoność wykładnicza).