Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.
Funkcja, która woła samą siebie
Wyobraź sobie, że stoisz w kolejce i chcesz wiedzieć, które jesteś. Nie widzisz początku, więc pytasz osobę przed sobą: „które jesteś?”. Ona nie wie, więc pyta osobę przed sobą. I tak dalej — aż pytanie dojdzie do pierwszej osoby, która odpowiada: „jestem pierwsza”. Wtedy odpowiedź wraca: druga, trzecia, czwarta… aż do Ciebie.
To jest dokładnie rekurencja. Funkcja, która nie umie odpowiedzieć od razu, zadaje to samo pytanie w mniejszej wersji — i czeka. Gdy odpowiedź w końcu wraca, dokłada do niej swoją część.
// suma 1 + 2 + ... + n, petla
int suma(int n) {
int wynik = 0;
for (int i = 1; i <= n; i++) {
wynik += i;
}
return wynik;
}
cout << suma(5);
// to samo, rekurencyjnie
int suma(int n) {
if (n == 0) return 0; // wiem od reki
return n + suma(n - 1); // pytam mniejsza wersje
}
cout << suma(5);
Prześledź prawą wersję dla n = 5. suma(5) nie umie odpowiedzieć, więc liczy 5 + suma(4). Ta woła 4 + suma(3), ta 3 + suma(2) i tak dalej, aż do suma(0), które zna odpowiedź bez pytania kogokolwiek i zwraca zero. Dopiero wtedy wyniki wracają w górę: 0 → 1 → 3 → 6 → 10 → 15.
#include <iostream>
using namespace std;
int suma(int n) {
cout << "wchodze do suma(" << n << ")\n";
if (n == 0) {
cout << " suma(0) = 0, wracam\n";
return 0;
}
int mniejsza = suma(n - 1);
int wynik = n + mniejsza;
cout << " suma(" << n << ") = " << wynik << ", wracam\n";
return wynik;
}
int main() {
cout << "WYNIK: " << suma(3);
return 0;
}
To wyjście warto przeczytać dwa razy. Zwróć uwagę, że wszystkie „wchodzę” wypisały się najpierw, a dopiero potem wszystkie „wracam” — i to w odwrotnej kolejności. Tak właśnie działa rekurencja: najpierw schodzisz na sam dół, potem wracasz zbierając wyniki po drodze.
Warunek stopu i krok w dół
Każda działająca funkcja rekurencyjna ma dokładnie dwie części. Brak którejkolwiek kończy się tak samo: program wysypuje się w ułamku sekundy.
warunek stopu
Sytuacja, w której funkcja zna odpowiedź od ręki i nie woła siebie dalej. Pisz go zawsze jako pierwszą linijkę.
krok w dół
Wywołanie siebie z mniejszym problemem. Musi realnie zbliżać do warunku stopu.
brak stopu
Funkcja woła siebie bez końca. Program kończy się błędem po ułamku sekundy — to tzw. przepełnienie stosu.
krok w bok
f(n) wołające f(n) albo f(n + 1) nigdy nie dojdzie do stopu. Sprawdź, czy argument naprawdę maleje.
stos wywołań
Każde czekające wywołanie zajmuje pamięć. Kilkadziesiąt tysięcy poziomów to już za dużo.
jak podejrzeć
Wstaw cout na wejściu i przed każdym return — zobaczysz całą drogę w dół i z powrotem.
#include <iostream>
using namespace std;
int silnia(int n) {
// 1. WARUNEK STOPU - zawsze na gorze
if (n <= 1) return 1;
// 2. KROK W DOL - argument MUSI malec
return n * silnia(n - 1);
}
int main() {
cout << silnia(5) << "\n"; // 120
cout << silnia(1) << "\n"; // 1 - sam warunek stopu
cout << silnia(0) << "\n"; // 1 - tez
return 0;
}
Zobacz, co się stanie, gdy zapomnisz warunku stopu albo napiszesz krok, który nie zmniejsza problemu. W obu przypadkach program nie zapętla się w nieskończoność jak pętla while — kończy się szybko, ale błędem.
// BRAK warunku stopu
int zle(int n) {
return n + zle(n - 1);
}
// zle(5) wola zle(4), zle(3), zle(2),
// zle(1), zle(0), zle(-1), zle(-2)...
// i tak w nieskonczonosc
// warunek stopu JEST, ale nigdy nie zajdzie
int zle(int n) {
if (n == 0) return 0;
return n + zle(n + 1); // ROSNIE!
}
// zle(5) wola zle(6), zle(7), zle(8)...
// zera nigdy nie zobaczy
Skąd ta nazwa? Komputer pamięta czekające wywołania na stosie — dokładnie tym samym, o którym jest osobny temat. Każde wejście do funkcji kładzie tam kolejną warstwę, każdy return ją zdejmuje. Gdy warstw zrobi się kilkadziesiąt tysięcy, miejsce się kończy — i to jest właśnie przepełnienie stosu.
Gdzie rekurencja naprawdę pomaga
Suma i silnia to przykłady szkolne — w praktyce napiszesz je pętlą. Rekurencja wygrywa tam, gdzie problem naturalnie dzieli się na mniejsze kopie samego siebie i nie wiadomo z góry, ile poziomów będzie.
// wypisz cyfry liczby OD LEWEJ do prawej
void cyfry(int n) {
if (n == 0) return;
cyfry(n / 10); // najpierw starsze cyfry
cout << n % 10 << " "; // potem ta ostatnia
}
int main() {
cyfry(4821);
return 0;
}
// a do potegi n
long long potega(long long a, int n) {
if (n == 0) return 1;
return a * potega(a, n - 1);
}
int main() {
cout << potega(2, 10);
return 0;
}
Lewy przykład to ładna sztuczka. Pętlą wypisanie cyfr od lewej jest kłopotliwe, bo % 10 daje je od prawej. W rekurencji wystarczy postawić cout po wywołaniu siebie — wtedy wypisze się dopiero w drodze powrotnej, czyli w odwrotnej kolejności.
To jest w ogóle najważniejsza rzecz do zapamiętania o rekurencji: kod przed wywołaniem wykonuje się w drodze w dół, a kod po wywołaniu — w drodze z powrotem. Przesunięcie jednej linijki zmienia całą kolejność.
#include <iostream>
using namespace std;
void odliczaj(int n) {
if (n == 0) return;
cout << n << " "; // w drodze W DOL
odliczaj(n - 1);
cout << n << " "; // w drodze W GORE
}
int main() {
odliczaj(4);
return 0;
}
Rekurencja kontra pętla
Rekurencja bywa elegancka, ale ma swoją cenę: każde czekające wywołanie zajmuje pamięć, a samo wejście do funkcji kosztuje odrobinę czasu. Dla prostych zadań pętla jest krótsza, szybsza i łatwiejsza do debugowania.
Jest też pułapka, która zaskakuje najbardziej: rekurencja potrafi liczyć to samo w kółko. Najsłynniejszy przykład to ciąg Fibonacciego, gdzie każdy wyraz to suma dwóch poprzednich.
long long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// fib(40) wykonuje ponad MILIARD wywolan,
// bo fib(38) liczy sie 2 razy,
// fib(37) - 3 razy, fib(36) - 5 razy...
// Czeka sie kilka sekund.
long long fib(int n) {
if (n <= 1) return n;
long long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
long long c = a + b;
a = b;
b = c;
}
return b;
}
// fib(40) to 39 obrotow petli. Natychmiast.
Obie funkcje dają tę samą odpowiedź. Różnica polega na tym, że wersja rekurencyjna rozgałęzia się na dwie strony i przelicza te same wartości tysiące razy. To nie jest wada rekurencji jako takiej — to wada tej konkretnej rekurencji, która wywołuje siebie więcej niż raz.
Prosta zasada na start: jeśli funkcja wywołuje siebie jeden raz, rekurencja jest bezpieczna i często czytelniejsza od pętli. Jeśli wywołuje siebie dwa razy lub więcej, policz na kartce, ile wywołań z tego wyjdzie — zanim uruchomisz.
Rekurencja w jednym miejscu
Rekurencja to tak naprawdę dwie linijki i jedna zasada. Reszta tabelki to rzeczy, na których najłatwiej się potknąć.
| Element | Co robi | Uwaga |
|---|---|---|
if (warunek) return wartosc; |
Warunek stopu — koniec schodzenia w dół. | Zawsze na górze funkcji |
return f(n - 1); |
Krok w dół z mniejszym argumentem. | Argument musi maleć |
kod przed f(...) |
Wykonuje się w drodze w dół. | Kolejność zgodna z wywołaniami |
kod po f(...) |
Wykonuje się w drodze z powrotem. | Kolejność odwrotna |
f(n/10) |
Krok po cyfrach liczby. | Rozkład liczby od lewej |
f(n-1) + f(n-2) |
Dwa wywołania naraz. | Rośnie lawinowo — licz, zanim uruchomisz |
brak warunku stopu |
Program kończy się błędem po ułamku sekundy. | Przepełnienie stosu |
głębokość ponad ~10⁴ |
Za dużo czekających wywołań. | Przepisz na pętlę |
Wiersze trzeci i czwarty to sedno całego tematu. cout postawiony przed wywołaniem wypisze cyfry od prawej, a postawiony po — od lewej. Jedna linijka przesunięta o jedno miejsce, zupełnie inny wynik.
Sprawdź się na zadaniach
Sześć zadań od najprostszego. W każdym zacznij od pytania: kiedy znam odpowiedź od ręki? To jest Twój warunek stopu, a reszta zwykle pisze się sama.
n wypisze liczby od n w dół do 1, a na końcu słowo Start!n spadnie do zera, wypisz Start! i zakończ. W przeciwnym razie wypisz n i zawołaj siebie z n - 1.Pokaż rozwiązanie
#include <iostream>
using namespace std;
void odliczaj(int n) {
if (n == 0) {
cout << "Start!";
return;
}
cout << n << " ";
odliczaj(n - 1);
}
int main() {
int n;
cin >> n;
odliczaj(n);
return 0;
}
n.n = 0 suma wynosi zero. W pozostałych przypadkach suma do n to n plus suma do n - 1.Pokaż rozwiązanie
#include <iostream>
using namespace std;
long long suma(int n) {
if (n == 0) return 0;
return n + suma(n - 1);
}
int main() {
int n;
cin >> n;
cout << suma(n);
return 0;
}
a podniesione do potęgi n (gdzie n jest nieujemne).a do n to a razy a do n-1. Weź long long, bo potęgi rosną szybko.Pokaż rozwiązanie
#include <iostream>
using namespace std;
long long potega(long long a, int n) {
if (n == 0) return 1;
return a * potega(a, n - 1);
}
int main() {
long long a;
int n;
cin >> a >> n;
cout << potega(a, n);
return 0;
}
4 8 2 1.% 10 daje cyfry od prawej. W rekurencji wystarczy postawić cout po wywołaniu siebie — wtedy wypisze się dopiero w drodze powrotnej.Pokaż rozwiązanie
#include <iostream>
using namespace std;
void cyfry(int n) {
if (n == 0) return;
cyfry(n / 10); // najpierw starsze cyfry
cout << n % 10 << " "; // dopiero potem ta ostatnia
}
int main() {
int n;
cin >> n;
if (n == 0) cout << 0; // zero to przypadek szczegolny
else cyfry(n);
return 0;
}
Pokaż rozwiązanie
#include <iostream>
#include <string>
using namespace std;
bool palindrom(const string& s, int lewy, int prawy) {
if (lewy >= prawy) return true; // spotkaly sie
if (s[lewy] != s[prawy]) return false; // roznica
return palindrom(s, lewy + 1, prawy - 1);
}
int main() {
string s;
cin >> s;
if (palindrom(s, 0, s.length() - 1)) cout << "TAK";
else cout << "NIE";
return 0;
}
n krążków różnej wielkości, ułożonych na pierwszym słupku od największego na dole. Przenieś wszystkie na trzeci słupek. Możesz przenosić po jednym krążku i nigdy nie wolno położyć większego na mniejszym. Wypisz kolejne ruchy.n krążków z A na C, przenieś najpierw n-1 górnych z A na B, potem ten największy z A na C, a na koniec te n-1 z B na C. Warunek stopu: zero krążków to zero ruchów.Pokaż rozwiązanie
#include <iostream>
using namespace std;
void hanoi(int n, char z, char na, char pomocniczy) {
if (n == 0) return;
hanoi(n - 1, z, pomocniczy, na);
cout << "Przenies krazek " << n << ": " << z << " -> " << na << "\n";
hanoi(n - 1, pomocniczy, na, z);
}
int main() {
int n;
cin >> n;
hanoi(n, 'A', 'C', 'B');
return 0;
}
Częste błędy i dobre praktyki
if, który kończy rekurencję. Bez niego program wysypie się po ułamku sekundy.f(n - 1) zbliża do stopu, f(n) i f(n + 1) — nie. Sprawdź to, zanim uruchomisz.cout na wejściu do funkcji i przed return pokazuje całą drogę. To najprostszy sposób, żeby zrozumieć, co się dzieje.