Rekurencja — metoda, która wywołuje samą siebie

Czego się dziś nauczysz

Przygotowanie: lekcje 01–20. Przewidywany czas: 45–90 minut z zadaniami. Przykłady wymagają .NET 8 lub nowszego, z włączonymi ImplicitUsings i Nullable.

Metoda, która wywołuje samą siebie

Wyobraź sobie, że stoisz w kolejce i chcesz wiedzieć, które masz miejsce. Zamiast liczyć wszystkich przed sobą, pytasz osobę stojącą przed tobą: „które masz miejsce?”. Ona pyta następną, ta następną — aż ktoś odpowie „jestem pierwszy”. Wtedy odpowiedzi wracają: druga, trzecia, czwarta… aż do ciebie.

Tak działa rekurencja: metoda rozwiązuje mniejszą wersję tego samego zadania, wywołując samą siebie. Każda taka metoda musi mieć dwie rzeczy:

• warunek bazowy — sytuacja, w której odpowiedź znamy od razu i nie wywołujemy siebie („jestem pierwszy”);
• krok rekurencyjny — wywołanie siebie z mniejszym zadaniem, które zbliża nas do warunku bazowego.

static long Silnia(int n)
{
    if (n <= 1)
    {
        return 1;              // WARUNEK BAZOWY - tu rekurencja sie konczy
    }

    return n * Silnia(n - 1);  // KROK REKURENCYJNY - mniejsze zadanie
}

Silnia liczby 4 to 4 · 3 · 2 · 1. Metoda liczy to tak:

Silnia(4)  ->  4 * Silnia(3)
Silnia(3)  ->  3 * Silnia(2)
Silnia(2)  ->  2 * Silnia(1)
Silnia(1)  ->  1                 <- warunek bazowy, koniec schodzenia

potem wyniki wracaja w gore:
Silnia(2) = 2 * 1  = 2
Silnia(3) = 3 * 2  = 6
Silnia(4) = 4 * 6  = 24

Skąd komputer wie, gdzie wrócić

Każde wywołanie metody dostaje własny komplet parametrów i zmiennych lokalnych. Środowisko odkłada je na stos wywołań i zdejmuje przy powrocie. Dlatego n w Silnia(4) i n w Silnia(3) to dwie różne zmienne, choć nazywają się tak samo.

Stos ma ograniczony rozmiar. Rekurencja bez warunku bazowego — albo taka, która się do niego nie zbliża — zapełni go i program przerwie się wyjątkiem StackOverflowException. Tego wyjątku nie da się przechwycić przez try: proces po prostu kończy pracę.

static int Zla(int n)
{
    return n + Zla(n - 1);   // BRAK warunku bazowego - program padnie
}

static int TezZla(int n)
{
    if (n == 0) return 0;
    return n + TezZla(n + 1);  // warunek jest, ale krok ODDALA sie od zera
}

Przykład: cztery klasyczne rekurencje

Wklej cały przykład do nowego projektu konsolowego jako Program.cs.

class Program
{
    // 1. silnia
    static long Silnia(int n)
    {
        if (n <= 1) return 1;
        return n * Silnia(n - 1);
    }

    // 2. suma cyfr liczby
    static int SumaCyfr(int n)
    {
        if (n < 10) return n;
        return n % 10 + SumaCyfr(n / 10);
    }

    // 3. odwrocenie napisu
    static string Odwroc(string tekst)
    {
        if (tekst.Length <= 1) return tekst;
        return Odwroc(tekst.Substring(1)) + tekst[0];
    }

    // 4. najwiekszy wspolny dzielnik - algorytm Euklidesa
    static int Nwd(int a, int b)
    {
        if (b == 0) return a;
        return Nwd(b, a % b);
    }

    static void Main()
    {
        Console.WriteLine($"Silnia(6)      = {Silnia(6)}");
        Console.WriteLine($"SumaCyfr(48317)= {SumaCyfr(48317)}");
        Console.WriteLine($"Odwroc(\"ROBOT\") = {Odwroc("ROBOT")}");
        Console.WriteLine($"Nwd(84, 36)    = {Nwd(84, 36)}");
    }
}

Silnia(6)      = 720
SumaCyfr(48317)= 23
Odwroc("ROBOT") = TOBOR
Nwd(84, 36)    = 12

Co dzieje się po kolei

• SumaCyfr(48317) odcina ostatnią cyfrę operatorem %, a resztę liczby przekazuje dalej przez / 10. Warunek bazowy to liczba jednocyfrowa.
• Odwroc najpierw odwraca ogon napisu, a dopiero potem dokłada pierwszą literę na koniec. Dlatego litera R ląduje na końcu wyniku.
• Nwd nie zmniejsza argumentu o jeden, tylko podmienia parę liczb. Krok też jest zmniejszaniem — reszta z dzielenia zawsze jest mniejsza od dzielnika.
• Typ long w silni nie jest ozdobą: Silnia(21) przekracza zakres long i wynik cicho się przekręci.

Rekurencja czy pętla

Każdą rekurencję da się zapisać pętlą, a każdą pętlę — rekurencją. Wybieramy to, co czytelniejsze dla konkretnego zadania.

Jest jeszcze pułapka kosztu. Naiwny ciąg Fibonacciego wywołuje się dwa razy w każdym kroku:

static int Fib(int n)
{
    if (n < 2) return n;
    return Fib(n - 1) + Fib(n - 2);   // dwa wywolania z jednego
}

Dla n = 40 to ponad trzysta milionów wywołań, bo te same wartości liczone są w kółko. Wersja z pętlą i dwiema zmiennymi daje wynik natychmiast. Rekurencja nie jest z natury wolniejsza — wolne jest powtarzanie tej samej pracy.

Użyte w tej lekcji elementy

Na co uważać

Co trzeba zapamiętać

• Metoda rekurencyjna potrzebuje warunku bazowego i kroku, który zbliża się do tego warunku.
• Wywołania odkładane są na stosie; każde ma własne parametry i zmienne lokalne.
• Brak albo nieosiągalny warunek bazowy kończy się StackOverflowException, którego nie przechwycisz.
• Instrukcje przed wywołaniem rekurencyjnym działają w drodze w dół, po nim — w drodze w górę.
• Rekurencja jest naturalna tam, gdzie zadanie samo dzieli się na mniejsze takie same zadania.
• Powtarzanie tych samych obliczeń (naiwny Fibonacci) jest kosztowne — wtedy lepsza jest pętla albo zapamiętywanie wyników.

Dokumentacja: Microsoft Learn — temat tej lekcji.