Rekurencja w Pythonie i C++ — przykłady na maturę 2026 (z kodem)

Rekurencja to jedno z tych pojęć w informatyce, które na początku wydaje się czarną magią, ale gdy raz je zrozumiesz, całkowicie zmienia sposób, w jaki myślisz o rozwiązywaniu problemów. Na maturze z informatyki zadania z rekurencji to pewniak – pojawiają się zarówno w części teoretycznej (analiza pseudokodu), jak i praktycznej (napisanie algorytmu). W tym, bardzo obszernym poradniku, rozełożymy rekurencję na czynniki pierwsze. Skupimy się na dwóch najbardziej klasycznych przykładach: silni oraz ciągu Fibonacciego.

Czym w ogóle jest rekurencja?

W dużym uproszczeniu: rekurencja to sytuacja, w której funkcja wywołuje samą siebie, aby rozwiązać mniejszy fragment tego samego problemu. Wyobraź sobie rosyjskie matrioszki. Otwierasz największą lalkę (problem główny), a w środku znajdujesz nieco mniejszą (podproblem). Otwierasz ją, i widzisz kolejną, jeszcze mniejszą. Robisz to tak długo, aż trafisz na najmniejszą, nieotwieralną lalkę. Ta najmniejsza lalka to w informatyce tzw. warunek brzegowy (przypadek bazowy).

Jak komputer radzi sobie z rekurencją? Poznaj Stos Wywołań (Call Stack)

Komputer musi zapamiętać, gdzie skończył wykonywać daną funkcję, zanim wywołał kolejną. Robi to za pomocą struktury danych zwanej stosem (stack). Działa to jak stos talerzy – odkładasz nowy wywołany program na górę stosu, a gdy się on zakończy, zdejmujesz go i wracasz do tego, co było pod spodem. Jeśli zapomnisz o warunku brzegowym, komputer będzie dokładał "talerze" w nieskończoność, aż zabraknie mu pamięci. Wtedy program wybuchnie, wyrzucając słynny błąd: Stack Overflow (Przepełnienie stosu).

Przykład 1: Obliczanie Silni (Factorial)

Zacznijmy od najprostszego, wręcz podręcznikowego przykładu rekurencji: silni. Silnia liczby całkowitej dodatniej n (zapisywana jako n!) to iloczyn wszystkich liczb całkowitych dodatnich nie większych niż n.

Matematyczna definicja silni wygląda tak: n! = 1 dla n = 0 n! = n · (n-1)! dla n > 0

Widzisz tę zależność? Aby obliczyć 5!, musisz wiedzieć ile to 4!. Aby znać 4!, potrzebujesz 3! i tak dalej, aż dojdziesz do 0!, które zawsze wynosi 1 (to jest nasz warunek brzegowy!).

Implementacja rekurencyjna w Pythonie

def silnia(n):
    # 1. Warunek brzegowy
    if n == 0:
        return 1
    # 2. Krok rekurencyjny
    else:
        return n * silnia(n - 1)

# Testujemy działanie
print("5! =", silnia(5))  # Wypisze: 120

Implementacja rekurencyjna w C++

#include <iostream>
using namespace std;

// Funkcja zwraca typ long long, ponieważ silnia rośnie bardzo szybko
long long silnia(int n) {
    // 1. Warunek brzegowy
    if (n == 0) {
        return 1;
    }
    // 2. Krok rekurencyjny
    return n * silnia(n - 1);
}

int main() {
    cout << "5! = " << silnia(5) << endl; // Wypisze: 120
    return 0;
}

Śledzenie wykonania (Trace) krok po kroku

Rozpiszmy teraz, co DOKŁADNIE dzieje się w pamięci komputera (na stosie wywołań), gdy wywołujemy funkcję silnia(4).

1. Start: Wywołanie silnia(4).
2. Czy n == 0? Nie. Zatem funkcja chce zwrócić 4 * silnia(3). Zanim pomnoży, musi obliczyć silnia(3). Czeka.
3. Zanurzenie 1: Wywołanie silnia(3).
4. Czy n == 0? Nie. Funkcja chce zwrócić 3 * silnia(2). Czeka.
5. Zanurzenie 2: Wywołanie silnia(2).
6. Czy n == 0? Nie. Funkcja chce zwrócić 2 * silnia(1). Czeka.
7. Zanurzenie 3: Wywołanie silnia(1).
8. Czy n == 0? Nie. Funkcja chce zwrócić 1 * silnia(0). Czeka.
9. Zanurzenie 4: Wywołanie silnia(0).
10. Czy n == 0? TAK! Trafiamy na warunek brzegowy. Funkcja zwraca 1. (Stos zaczyna się "zwijać").
11. Wynurzanie 1: silnia(1) otrzymuje wartość 1 od silnia(0). Mnoży 1 · 1 = 1. Zwraca 1 wyżej.
12. Wynurzanie 2: silnia(2) otrzymuje wartość 1. Mnoży 2 · 1 = 2. Zwraca 2 wyżej.
13. Wynurzanie 3: silnia(3) otrzymuje wartość 2. Mnoży 3 · 2 = 6. Zwraca 6 wyżej.
14. Wynurzanie 4: silnia(4) otrzymuje wartość 6. Mnoży 4 · 6 = 24. Zwraca ostateczny wynik: 24.

To "zwijanie" stosu to najbardziej charakterystyczna cecha rekurencji. Operacja (w tym wypadku mnożenie) jest wykonywana dopiero w momencie, gdy funkcja wraca z głębin rekurencji.

Przykład 2: Ciąg Fibonacciego (Pułapka Naiwnej Rekurencji)

Ciąg Fibonacciego to klasyk maturalny. Jest to ciąg liczb, w którym każdy kolejny wyraz jest sumą dwóch poprzednich. Matematyczna definicja wygląda tak:

F_0 = 0 F_1 = 1 F_n = F_{n-1} + F_{n-2} dla n > 1

Na pierwszy rzut oka, definicja ta aż prosi się o zaimplementowanie jej za pomocą rekurencji. Zobaczmy, jak wyglądałby kod.

Naiwna implementacja rekurencyjna (Python)

def fib(n):
    # Warunki brzegowe (mamy dwa, bo wzór odwołuje się do dwóch wstecz!)
    if n == 0:
        return 0
    if n == 1:
        return 1
        
    # Krok rekurencyjny
    return fib(n - 1) + fib(n - 2)

# Policzmy 6. wyraz ciągu
print("F(6) =", fib(6))  # Wypisze: 8

Naiwna implementacja rekurencyjna (C++)

#include <iostream>
using namespace std;

long long fib(int n) {
    // Warunki brzegowe
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Krok rekurencyjny
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << "F(6) = " << fib(6) << endl; // Wypisze: 8
    return 0;
}

Dlaczego to jest "naiwne"? Problem złożoności wykładniczej

Kod napisany powyżej jest bardzo elegancki i czytelny, ale posiada absolutnie tragiczną wydajność. Jeśli spróbujesz za jego pomocą policzyć fib(50), program prawdopodobnie zawiesi się na bardzo długi czas (minuty, a nawet godziny). Dlaczego tak się dzieje?

Narysujmy drzewo wywołań dla zaledwie fib(5): Aby policzyć fib(5), funkcja wywołuje fib(4) oraz fib(3). Aby policzyć fib(4), funkcja wywołuje fib(3) oraz fib(2). Aby policzyć fib(3), funkcja wywołuje fib(2) oraz fib(1).

Optymalizacja: Memoizacja (Sprytna rekurencja)

Jeśli chcemy pozostać przy rekurencji (co czasem jest wymuszone w zadaniach), musimy użyć techniki zwanej memoizacją (od słowa 'memo' - zapamiętywać, to nie jest błąd ortograficzny, to nie 'memoraryzacja'). Polega ona na tym, że gdy obliczymy jakiś wyraz ciągu Fibonacciego, zapisujemy go w tablicy lub słowniku. Przy kolejnym wywołaniu funkcji z tym samym argumentem, po prostu odczytujemy wynik z pamięci, zamiast liczyć go od nowa.

Memoizacja w Pythonie (Ręczna)

# Tworzymy słownik do przechowywania wyników. 
# Inicjalizujemy go warunkami brzegowymi.
cache = {0: 0, 1: 1}

def fib_memo(n):
    # Sprawdzamy, czy wynik jest już w pamięci
    if n in cache:
        return cache[n]
        
    # Jeśli nie ma, obliczamy go rekurencyjnie
    wynik = fib_memo(n - 1) + fib_memo(n - 2)
    
    # Zapisujemy w pamięci przed zwróceniem
    cache[n] = wynik
    
    return wynik

# Teraz fib_memo(50) wykona się w ułamek sekundy!
print("F(50) =", fib_memo(50))

Python: "Oszustwo" maturalne z dekoratorem

Python ma wbudowaną funkcję robiącą to automatycznie! Jeśli w zadaniu możesz pisać swobodnie, użyj modułu functools.

from functools import lru_cache

# Dekorator automatycznie buforuje wyniki wywołań funkcji
@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print("F(100) =", fib_fast(100))

Memoizacja w C++

#include <iostream>
#include <vector>
using namespace std;

// Tworzymy wektor wypełniony wartością -1, co oznacza "jeszcze nie obliczono"
vector<long long> memo(1000, -1);

long long fib_memo(int n) {
    if (n <= 1) return n;
    
    // Jeśli wartość była już obliczona, zwróć ją z wektora
    if (memo[n] != -1) {
        return memo[n];
    }
    
    // W przeciwnym razie oblicz, ZAPISZ w wektorze i zwróć
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main() {
    cout << "F(50) = " << fib_memo(50) << endl;
    return 0;
}

Rozwiązanie Ostateczne: Iteracja (Pętla)

Mimo że memoizacja jest super, każde wywołanie rekurencyjne wciąż zajmuje miejsce na stosie (pamięć O(n)). Jeśli na maturze proszą Cię o napisanie optymalnego algorytmu dla ciągu Fibonacciego, i nie narzucają rekurencji, ZAWSZE używaj iteracji (pętli). Złożoność czasowa to wciąż O(n), ale złożoność pamięciowa spada do O(1) (używamy tylko kilku zmiennych pomocniczych).

Fibonacci Iteracyjnie (Pętla) - Python

def fib_iter(n):
    if n == 0: return 0
    if n == 1: return 1
    
    a = 0  # F(n-2)
    b = 1  # F(n-1)
    
    for i in range(2, n + 1):
        # Zapisujemy nową wartość (a + b) i przesuwamy zmienne
        nastepny = a + b
        a = b
        b = nastepny
        
    return b

print(fib_iter(50))

Fibonacci Iteracyjnie (Pętla) - C++

#include <iostream>
using namespace std;

long long fib_iter(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    long long a = 0;
    long long b = 1;
    long long nastepny;
    
    for(int i = 2; i <= n; i++) {
        nastepny = a + b;
        a = b;
        b = nastepny;
    }
    
    return b;
}

int main() {
    cout << fib_iter(50) << endl;
    return 0;
}

Przykładowe zadanie maturalne z rozwiązaniem krok po kroku

Zobaczmy, jak może wyglądać typowe zadanie analizujące algorytm rekurencyjny. Wykorzystamy tu inny popularny maturalny klasyk: Algorytm Euklidesa do szukania Największego Wspólnego Dzielnika (NWD).

Krok po kroku: Jak to rozwiązać na kartce?

Najlepszą metodą na takie zadania jest metoda "tabelki wywołań". Zapisujemy po kolei, z jakimi argumentami wywoływana jest funkcja i co oblicza z tych argumentów.

1. Wywołanie 1: algo(12, 18). Zmienne: a = 12, b = 18. Czy b == 0? Nie (18 != 0). Wykonujemy resztę z dzielenia: 12 mod 18 = 12 (bo 12 dzieli się przez 18 równe 0 razy i zostaje 12 reszty). Funkcja zwraca wywołanie: algo(18, 12).
2. Wywołanie 2: algo(18, 12). Zmienne: a = 18, b = 12. Czy b == 0? Nie. Wykonujemy: 18 mod 12 = 6. Funkcja zwraca wywołanie: algo(12, 6).
3. Wywołanie 3: algo(12, 6). Zmienne: a = 12, b = 6. Czy b == 0? Nie. Wykonujemy: 12 mod 6 = 0. Funkcja zwraca wywołanie: algo(6, 0).
4. Wywołanie 4: algo(6, 0). Zmienne: a = 6, b = 0. Czy b == 0? TAK! Funkcja zwraca wartość a, czyli 6. Rekurencja się kończy.

Odpowiedź dla egzaminatora: Program zwróci wartość: 6. Pary parametrów wywołań: (12, 18), (18, 12), (12, 6), (6, 0).

Najczęściej zadawane pytania (FAQ)

Masz już potężną pigułkę wiedzy. Zrozumienie, jak komputer używa stosu do powrotu z wcześniejszych wywołań, to klucz do opanowania rekurencji. Uruchom powyższe kody w swoim ulubionym środowisku IDE, wstaw instrukcje wypisujące print/cout wewnątrz funkcji i poobserwuj sam, jak algorytm "zanurza się" i "wynurza".

Chcesz nauczyć się tego na maturę? Sprawdź nasz kurs do matury z informatyki.