C++ · Podstawy · Rekurencja

Rekurencja w C++

Funkcja, która wywołuje samą siebie. Brzmi jak błąd, a bywa najprostszym sposobem na problem, który inaczej wymagałby dziesięciu pętli.

Filmy z OKI

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ć.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

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ęść.

petla.cpp
// 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);
▶ Wyjście programu
15
rekurencja.cpp
// 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);
▶ Wyjście programu
15

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.

sledzenie.cpp
#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;
}
▶ Wyjście programu
wchodze do suma(3) wchodze do suma(2) wchodze do suma(1) wchodze do suma(0) suma(0) = 0, wracam suma(1) = 1, wracam suma(2) = 3, wracam suma(3) = 6, wracam WYNIK: 6

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.

dwa_elementy.cpp
#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;
}
▶ Wyjście programu
120 1 1

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.

bez_stopu.cpp
// 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
▶ Wyjście programu
Program konczy sie bledem (przepelnienie stosu)
krok_w_bok.cpp
// 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
▶ Wyjście programu
Program konczy sie bledem (przepelnienie stosu)

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.

cyfry.cpp
// 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;
}
▶ Wyjście programu
4 8 2 1
potega.cpp
// 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;
}
▶ Wyjście programu
1024

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ść.

w_dol_i_w_gore.cpp
#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;
}
▶ Wyjście programu
4 3 2 1 1 2 3 4

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.

fib_rekurencja.cpp
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.
▶ Wyjście programu
kilka sekund
fib_petla.cpp
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.
▶ Wyjście programu
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ąć.

ElementCo robiUwaga
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.

Łatwe Odliczanie
Napisz funkcję rekurencyjną, która dla podanego n wypisze liczby od n w dół do 1, a na końcu słowo Start!
Jak to ugryźć: Warunek stopu: gdy n spadnie do zera, wypisz Start! i zakończ. W przeciwnym razie wypisz n i zawołaj siebie z n - 1.
Pokaż rozwiązanie
odliczanie.cpp
#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;
}
Łatwe Suma od 1 do n
Napisz funkcję rekurencyjną liczącą sumę wszystkich liczb od 1 do n.
Jak to ugryźć: Kiedy znasz odpowiedź od ręki? Dla n = 0 suma wynosi zero. W pozostałych przypadkach suma do n to n plus suma do n - 1.
Pokaż rozwiązanie
suma.cpp
#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;
}
Łatwe Potęga
Napisz funkcję rekurencyjną liczącą a podniesione do potęgi n (gdzie n jest nieujemne).
Jak to ugryźć: Cokolwiek do potęgi zerowej daje 1 — to Twój warunek stopu. Poza tym a do n to a razy a do n-1. Weź long long, bo potęgi rosną szybko.
Pokaż rozwiązanie
potega.cpp
#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;
}
Średnie Cyfry od lewej
Napisz funkcję rekurencyjną, która wypisze cyfry liczby oddzielone spacjami, w normalnej kolejności — od lewej do prawej. Dla 4821 wynikiem jest 4 8 2 1.
Jak to ugryźć: Pętlą to jest kłopotliwe, bo % 10 daje cyfry od prawej. W rekurencji wystarczy postawić cout po wywołaniu siebie — wtedy wypisze się dopiero w drodze powrotnej.
Pokaż rozwiązanie
cyfry.cpp
#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;
}
Średnie Palindrom rekurencyjnie
Napisz funkcję rekurencyjną sprawdzającą, czy słowo czyta się tak samo od przodu i od tyłu.
Jak to ugryźć: Funkcja dostaje napis oraz dwie pozycje: lewą i prawą. Warunek stopu: gdy pozycje się miną albo spotkają, to palindrom. W przeciwnym razie porównaj skrajne znaki i — jeśli są równe — zawołaj siebie z pozycjami przesuniętymi do środka.
Pokaż rozwiązanie
palindrom.cpp
#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;
}
Trudne Wieże z Hanoi
Masz trzy słupki i 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.
Jak to ugryźć: Klasyk, który pętlą pisze się okropnie, a rekurencją w cztery linijki. Pomysł: żeby przenieść 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
hanoi.cpp
#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

🛑
Warunek stopu jako pierwsza linijka
Zanim napiszesz cokolwiek innego, napisz if, który kończy rekurencję. Bez niego program wysypie się po ułamku sekundy.
⬇️
Argument musi maleć
f(n - 1) zbliża do stopu, f(n) i f(n + 1) — nie. Sprawdź to, zanim uruchomisz.
🧱
Przepełnienie stosu
Kilkadziesiąt tysięcy zagnieżdżonych wywołań to granica. Jeśli rekurencja ma sięgnąć głębiej, przepisz ją na pętlę.
↕️
Przed czy po wywołaniu
Kod przed wywołaniem wykonuje się w drodze w dół, po — w drodze z powrotem. Przesunięcie jednej linijki odwraca kolejność.
👁️
Wypisuj, żeby zobaczyć
cout na wejściu do funkcji i przed return pokazuje całą drogę. To najprostszy sposób, żeby zrozumieć, co się dzieje.
⚡
Dwa wywołania to sygnał ostrzegawczy
Funkcja wołająca siebie raz jest bezpieczna. Dwa razy — policz, ile wywołań z tego wyjdzie, bo rośnie to lawinowo.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.