Lekcja 20. Rekurencja
ŚredniPo co się tego uczymy?
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.
Teoria
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ą".
Schemat
Silnia(4) = 4 * Silnia(3)
|
4 * (3 * Silnia(2))
|
4 * (3 * (2 * Silnia(1)))
|
4 * (3 * (2 * 1)) <- przypadek bazowy, Silnia(1) = 1
Wywołania "schodzą w dół" (każde czeka na wynik następnego),
a potem "wracają w górę" mnożąc po drodze:
Silnia(4)
└─ 4 * Silnia(3)
└─ 3 * Silnia(2)
└─ 2 * Silnia(1)
└─ zwraca 1 (przypadek bazowy — tu się zatrzymujemy!)
zwraca 2 * 1 = 2
zwraca 3 * 2 = 6
zwraca 4 * 6 = 24
Przykład z życia
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.
Kod (C#)
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)}");
}
}Komentarz i wyjaśnienie kodu
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.
Ćwiczenie samodzielne
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?
Plac zabaw — wypróbuj online
Poniższy kod wykonuje się od razu w Twojej przeglądarce — nic nie trzeba instalować. Zmień kod i kliknij „Uruchom”.
Zadania do pracy własnej
Napisz metodę rekurencyjną
CzyPalindrom, która sprawdza, czy tekst czyta się tak samo od przodu i od tyłu (np. "kajak"). Podpowiedź: przypadek bazowy to tekst o długości 0 lub 1.Napisz metodę rekurencyjną obliczającą n-ty wyraz ciągu Fibonacciego (0, 1, 1, 2, 3, 5, 8, 13...). Uruchom ją dla n=35 i zaobserwuj, jak długo się liczy — potem zastanów się (albo poszukaj hasła "memoizacja"), dlaczego jest to aż tak wolne.
Napisz metodę rekurencyjną, która wypisuje wszystkie sposoby wydania danej kwoty za pomocą monet o nominałach 1, 2 i 5 groszy (bez powtarzania tych samych kombinacji w innej kolejności).
Typowe błędy
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.
Nawiązanie do egzaminu zawodowego
Rekurencja to jeden z algorytmów wymienionych wprost w podstawie programowej (INF.04.3.3 — "algorytmy iteracyjne, tekstowe, szyfrowania, tablicowe, rekurencyjne") oraz w zasadach programowania obiektowego (INF.04.4.2). Na egzaminie może pojawić się jako zadanie "napisz funkcję rekurencyjną obliczającą..." albo jako pytanie teoretyczne o przypadek bazowy i stos wywołań.