INF.04 · C# · lekcja 20

Rekurencja

Zobacz stos wywołań rekurencji

  • Zrozum
  • Sprawdź
  • Napisz sam

Po tej lekcji: zobacz stos wywołań rekurencji

Dzisiaj zrobisz konkretną rzecz

Niektóre problemy naturalnie definiuje się "przez samego siebie" — silnia liczby, przeszukiwanie folderów i podfolderów na dysku, przechodzenie po drzewie komentarzy pod postem, algorytm dziel-i-zwyciężaj. Rekurencja to metoda pisania takich rozwiązań: funkcja, która w swoim ciele wywołuje samą siebie. To jeden z efektów kształcenia w podstawie programowej (INF.04.4.2) i regularnie pojawia się na egzaminie, dlatego trzeba to rozumieć, a nie tylko przepisać wzór.

Eksplorator plików w Windows, kiedy liczysz rozmiar folderu, musi zajrzeć do każdego podfolderu, a w nim do kolejnych podfolderów, i tak dalej, aż trafi na same pliki (przypadek bazowy). To naturalna rekurencja — struktura folderów sama w sobie jest rekurencyjna (folder może zawierać foldery). Podobnie działa wyświetlanie komentarzy z odpowiedziami na odpowiedzi pod artykułem, albo menu firmy z działami i poddziałami.

Sprawdź w działaniu

Zobacz stos wywołań rekurencji

Najpierw przewidź wynik. Zmień dane w modelu i porównaj efekt. Spróbuj także przypadku granicznego, a nie tylko pierwszego poprawnego przykładu.

Ta interakcja wymaga włączonego JavaScriptu.

Model pokazuje wybraną zasadę. Nie uruchamia ani nie ocenia wklejonego kodu C#.

1. Przygotuj i uruchom własny projekt

2. Najpierw mały przykład

Wykonaj tę próbę przed dłuższym rozwiązaniem. Przypadek bazowy kończy wywołania. n-1 zmniejsza problem. Po dojściu do bazy wyniki wracają w odwrotnej kolejności. Granica20 chroni zakres long; to nie dowolnie duża matematyczna liczba.

Program.cscsharp
Console.WriteLine(Silnia(4));

static long Silnia(int n)
{
    if (n < 0 || n > 20) throw new ArgumentOutOfRangeException(nameof(n));
    if (n <= 1) return 1;
    return n * Silnia(n - 1);
}
Wynik
24; sprawdź też0 i1.
  1. Co sprawdzić? Zmień jedną wartość i przed uruchomieniem zapisz przewidywany rezultat. Porównaj go z opisem wyniku; przy błędzie wróć do konkretnej instrukcji.

Jak to działa — 1

Funkcja rekurencyjna składa się zawsze z dwóch elementów:

• przypadku bazowego (ang. base case) — najprostszej wersji problemu, którą da się rozwiązać wprost, bez dalszego wywoływania funkcji. To "hamulec", który zatrzymuje rekurencję;

• kroku rekurencyjnego — rozbicia problemu na mniejszy podobny problem i wywołania funkcji samej na sobie z tym mniejszym problemem.

Jeśli zabraknie przypadku bazowego (albo jest błędny), funkcja będzie wywoływać samą siebie w nieskończoność, aż program wyrzuci błąd StackOverflowException — pamięć przeznaczona na wywołania funkcji ("stos wywołań") się skończy. To najczęstszy błąd początkujących.

Każde wywołanie rekurencyjne trafia na stos wywołań i czeka tam, aż wywołanie, które samo uruchomiło, zwróci wynik. Dlatego rekurencja "schodzi w dół" do przypadku bazowego, a potem wyniki "wracają w górę", łącząc się po drodze (zobacz schemat).

Rekurencja nie jest jedyną metodą — prawie każdy algorytm rekurencyjny da się też zapisać iteracyjnie (przez pętlę). Czasem wersja iteracyjna jest szybsza i zużywa mniej pamięci, ale wersja rekurencyjna bywa dużo czytelniejsza dla problemów, które same w sobie mają strukturę drzewiastą lub "zagnieżdżoną".

3. Pełny przykład — czytaj od Main

Teraz zastąp Program.cs tym programem. Zanim uruchomisz, znajdź dane wejściowe, operację i miejsce prezentacji wyniku. W tym wariancie zachowujemy jawny Main. Nie wklejaj kilku pełnych programów do jednego pliku.

Program.cs — osobne uruchomieniecsharp
using System;

class Program
{
    // Silnia liczby n (n!) metodą rekurencyjną.
    static long Silnia(int n)
    {
        // Przypadek bazowy — silnia z 0 i z 1 wynosi 1.
        // Bez tego warunku funkcja wywoływałaby się w nieskończoność.
        if (n <= 1)
        {
            return 1;
        }

        // Krok rekurencyjny: n! = n * (n-1)!
        return n * Silnia(n - 1);
    }

    // Suma cyfr liczby, też rekurencyjnie.
    static int SumaCyfr(int liczba)
    {
        if (liczba < 10)
        {
            return liczba; // przypadek bazowy: jedna cyfra
        }

        return liczba % 10 + SumaCyfr(liczba / 10);
    }

    static void Main()
    {
        Console.WriteLine($"5! = {Silnia(5)}");
        Console.WriteLine($"Suma cyfr 4829 = {SumaCyfr(4829)}");
    }
}
  1. Prześledź kod Silnia(n) najpierw sprawdza przypadek bazowy (n <= 1) — jeśli go nie ma, funkcja zwraca 1 od razu, bez dalszych wywołań. Jeśli warunek nie jest spełniony, funkcja wywołuje samą siebie z mniejszym argumentem (n - 1) i mnoży wynik przez n. Dzięki temu, że argument za każdym razem maleje, funkcja prędzej czy później dotrze do przypadku bazowego. SumaCyfr działa podobnie, ale "obcina" liczbę z prawej strony przez dzielenie całkowite (liczba / 10) i dodaje ostatnią cyfrę (liczba % 10) do wyniku wywołania rekurencyjnego dla reszty liczby.

Sprawdź, zanim przepiszesz cały program

Brak przypadku bazowego albo błędny warunek — program "zawiesza się" i po chwili wywala StackOverflowException. Zawsze najpierw zapisz na kartce: "kiedy funkcja może odpowiedzieć bez dalszego wywoływania samej siebie?".

Argument nie maleje w kierunku przypadku bazowego — np. pomyłkowe wywołanie Silnia(n) zamiast Silnia(n - 1) tworzy nieskończoną pętlę wywołań identyczną jak brak przypadku bazowego.

Nadużywanie rekurencji tam, gdzie prosta pętla wystarczy — rekurencja zużywa pamięć stosu i jest zwykle wolniejsza niż pętla. Dobieraj narzędzie do problemu: jeśli struktura nie jest "zagnieżdżona" (jak drzewo czy foldery), zwykła pętla for/while często będzie lepszym wyborem.

Ćwiczenie z pomocą · samodzielna praca

4. Teraz Twoja zmiana

Napisz rekurencyjną metodę SumaDo(int n), która liczy sumę liczb od 1 do n (np. SumaDo(5) = 1+2+3+4+5 = 15). Zastanów się najpierw: jaki jest przypadek bazowy? Jaki jest krok rekurencyjny?

Oczekiwany rezultat
Spełnij warunki polecenia. Zapisz wejście, otrzymany wynik i wyjaśnij, która część kodu za niego odpowiada.
Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź

Wróć do podstawowej formy oraz objaśnienia: Przypadek bazowy kończy wywołania. n-1 zmniejsza problem. Po dojściu do bazy wyniki wracają w odwrotnej kolejności. Granica20 chroni zakres long; to nie dowolnie duża matematyczna liczba.

Krok 2 — pokaż podpowiedź

Zmień tylko część potrzebną do polecenia. Zachowaj działającą wersję przed zmianą i uruchamiaj po każdym małym etapie.

Krok 3 — pokaż podpowiedź

Sprawdź przypadek zwykły i graniczny; porównaj z regułą: 24; sprawdź też0 i1.

Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.

5. Sprawdź rozumienie, nie tylko uruchomienie

Dalej na swoim koncie

Rozgrzewki, quiz i zadania są w biurku ucznia.

Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.

Zaloguj się →
Źródła i dalsza nauka