Rekurencja (Matura Informatyka) - Jak to Zrozumieć w 5 Minut? (Python/C++)

Jedną z podstawowych definicji, z którą należy się zapoznać, ucząc się programowania, jest rekurencja. Przydaje się ona przy tworzeniu kodu, o czym przekonało się już wielu programistów. Jej znajomość jest też wymagana na maturze z informatyki. W tym artykule przeprowadzimy Cię krok po kroku przez wszystko, co musisz wiedzieć o rekurencji.

Co to jest rekurencja w informatyce?

Rekurencja (rekursja) to odwołanie się funkcji do samej siebie w trakcie działania programu. Wystarczy nawet pojedyncze wywołanie się procedury przez samą siebie, żeby uznać ją za rekurencyjną. Brzmi skomplikowanie? Spokojnie - za chwilę zobaczysz, że to prostsze niż myślisz.

Wyobraź sobie, że stoisz przed lustrem, a za Tobą jest drugie lustro. Widzisz nieskończone odbicia samego siebie - każde mniejsze od poprzedniego. Rekurencja działa podobnie: funkcja wywołuje samą siebie, ale za każdym razem z "mniejszym" problemem, aż dojdzie do przypadku podstawowego (bazowego), który można rozwiązać bezpośrednio.

Przykład rekurencji - obliczanie silni

Silnia liczby n (zapisywana jako n!) to iloczyn wszystkich liczb naturalnych od 1 do n. Na przykład: 5! = 5 · 4 · 3 · 2 · 1 = 120. Można to zapisać rekurencyjnie, zauważając że n! = n · (n-1)!

funkcja Silnia(n)
    jeżeli n = 0 lub n = 1 wykonuj
        zwróć 1
    zwróć n * Silnia(n - 1)

Wykonanie powyższego kodu dla n = 3 wygląda następująco (każde wcięcie to kolejny poziom wywołania rekurencyjnego):

1. Silnia(3) – Warunek nie jest spełniony (bo n = 3), więc przechodzimy do mnożenia: 3 · Silnia(2)
2. Silnia(2) – Warunek nie jest spełniony (bo n = 2), więc: 2 · Silnia(1)
3. Silnia(1) – Warunek JEST spełniony (bo n = 1), więc zwracamy 1
4. Powrót do Silnia(2) – Mnożymy wynik z Silnia(1) (czyli 1) przez 2, wynik = 2
5. Powrót do Silnia(3) – Mnożymy wynik z Silnia(2) (czyli 2) przez 3, wynik = 6

Kluczowe elementy każdej funkcji rekurencyjnej

1. Przypadek bazowy (warunek brzegowy) – sytuacja, w której funkcja zwraca wynik BEZ wywoływania samej siebie. To "dno" rekurencji, które zatrzymuje nieskończone wywołania.
2. Przypadek rekurencyjny – sytuacja, w której funkcja wywołuje samą siebie, ale z MNIEJSZYM lub PROSTSZYM problemem. Krok po kroku zbliżamy się do przypadku bazowego.

Rodzaje rekurencji

Rekurencja dzieli się na różne typy w zależności od sposobu wywołania oraz liczby wywołań. Znajomość tych podziałów pomoże Ci lepiej zrozumieć działanie rekurencji w kodzie.

Podział według sposobu wywołania

Rekurencja bezpośrednia jest spotykana znacznie częściej i łatwiejsza do analizy.

Podział według wzrostu liczby wywołań

Rekurencja nieliniowa może prowadzić do ogromnej liczby wywołań. Na przykład dla ciągu Fibonacciego obliczenie fib(50) naiwną metodą rekurencyjną wymagałoby miliardów wywołań!

Rekurencja ogonowa - szczególny przypadek

Rekurencja ogonowa (tail recursion) występuje wtedy, gdy ostatnią instrukcją funkcji jest wywołanie rekurencyjne. Dlaczego to ważne? Kompilatory wielu języków potrafią zoptymalizować taką rekurencję, zamieniając ją na pętlę, co eliminuje problem przepełnienia stosu.

# Zwykła rekurencja (NIE ogonowa)
def silnia(n):
    if n <= 1:
        return 1
    return n * silnia(n - 1)  # Po wywołaniu rekurencyjnym jest jeszcze mnożenie!

# Rekurencja ogonowa
def silnia_ogonowa(n, akumulator=1):
    if n <= 1:
        return akumulator
    return silnia_ogonowa(n - 1, n * akumulator)  # Ostatnia instrukcja = wywołanie

Ciąg Fibonacciego - klasyczny przykład rekurencji

Ciąg Fibonacciego to jeden z najpopularniejszych przykładów rekurencji. Jest to ciąg liczb naturalnych, w którym każda liczba jest sumą dwóch poprzednich: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Definicja matematyczna: fib(1) = 1, fib(2) = 1, a dla n > 2: fib(n) = fib(n-1) + fib(n-2)

Implementacja rekurencyjna

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

# Przykład użycia
for i in range(1, 11):
    print(fib(i), end=" ")
# Wynik: 1 1 2 3 5 8 13 21 34 55

Powyższy kod jest elegancki i prosty, ale ma poważny problem z wydajnością. Spójrz na drzewo wywołań dla fib(6):

                    fib(6)
                   /      \
              fib(5)        fib(4)
             /    \         /    \
        fib(4)  fib(3)   fib(3) fib(2)
        /   \    /  \     /  \
    fib(3) fib(2) fib(2) fib(1) fib(2) fib(1)
    /   \
 fib(2) fib(1)

Implementacja iteracyjna (znacznie wydajniejsza)

def fib_iteracyjnie(n):
    if n <= 2:
        return 1
    
    przedwczesniej = 0
    wczesniej = 1
    teraz = 1
    
    for i in range(2, n):
        przedwczesniej = wczesniej
        wczesniej = teraz
        teraz = przedwczesniej + wczesniej
    
    return teraz

# Teraz możemy bez problemu obliczyć nawet fib(1000)!
print(fib_iteracyjnie(50))  # Działa w ułamku sekundy

Rekurencja – zalety i wady

Większość początkujących programistów nie jest zaznajomiona z zaletami oraz wadami rekurencji. Warto je poznać, żeby świadomie decydować, kiedy warto jej użyć.

Zalety rekurencji

• Zwięzły i czytelny kod – dla problemów o rekurencyjnej naturze (drzewa, grafy, dziel i zwyciężaj) kod rekurencyjny bywa znacznie krótszy i łatwiejszy do zrozumienia
• Naturalność zapisu – niektóre algorytmy są definiowane rekurencyjnie z natury (silnia, Fibonacci, przeszukiwanie drzew), więc rekurencyjny kod odzwierciedla matematyczną definicję
• Możliwość udowodnienia poprawności – za pomocą indukcji matematycznej można formalnie dowieść, że algorytm rekurencyjny działa poprawnie dla wszystkich przypadków
• Memoizacja (caching) – można zoptymalizować algorytm rekurencyjny, zapisując wyniki powtarzających się wywołań, co drastycznie zmniejsza liczbę obliczeń

Wady rekurencji

• Jest pamięciochłonna – każde wywołanie funkcji wymaga miejsca na stosie (stack) do przechowywania zmiennych lokalnych i adresu powrotu. Głęboka rekurencja może przepełnić stos
• Może być wolna – narzut związany z wywołaniami funkcji (tworzenie ramki stosu, skok) spowalnia działanie w porównaniu z prostą pętlą
• Jest mniej intuicyjna dla początkujących – wymaga myślenia w kategoriach "zaufaj rekurencji" i zrozumienia, jak działa stos wywołań
• Ryzyko nieskończonej rekurencji – źle zdefiniowany warunek bazowy prowadzi do błędu Stack Overflow

Zapytani o rekurencję, doświadczeni programiści często odpowiadają: "unikamy, kiedy się da". Nie znaczy to, że rekurencja jest zła – po prostu wymaga świadomego stosowania. Dla wielu problemów (np. przeszukiwanie drzew, algorytmy dziel i zwyciężaj) jest naturalnym i eleganckim rozwiązaniem.

Kiedy używać rekurencji, a kiedy iteracji?

Oto praktyczny przewodnik, który pomoże Ci podjąć właściwą decyzję:

Używaj rekurencji, gdy:

• Problem ma rekurencyjną naturę – np. przeszukiwanie drzew, algorytmy dziel i zwyciężaj (Quicksort, Merge Sort), Wieże Hanoi
• Struktura danych jest rekurencyjna – drzewa binarne, grafy, listy powiązane – naturalnie nadają się do rekurencyjnego przetwarzania
• Problem można podzielić na identyczne podproblemy – jeśli rozwiązanie całości to kombinacja rozwiązań mniejszych, identycznych fragmentów
• Czytelność kodu jest priorytetem – rekurencyjny zapis bywa znacznie krótszy i bliższy matematycznej definicji

Używaj iteracji (pętli), gdy:

• Problem jest prosty i liniowy – sumowanie elementów tablicy, proste przeszukiwanie – pętla będzie prostsza
• Zależy Ci na wydajności – iteracja nie ma narzutu związanego z wywołaniami funkcji
• Musisz kontrolować zużycie pamięci – głęboka rekurencja może przepełnić stos
• Kod będą czytać początkujący programiści – dla wielu osób pętla jest bardziej intuicyjna

Przykłady algorytmów rekurencyjnych

Rekurencja jest szeroko stosowana w informatyce. Oto najważniejsze algorytmy, które warto znać:

• Silnia (Factorial) – klasyczny przykład rekurencji liniowej
• Ciąg Fibonacciego – przykład rekurencji nieliniowej (wymaga optymalizacji!)
• Wyszukiwanie binarne (Binary Search) – dzielenie przedziału na pół
• Sortowanie szybkie (Quicksort) – dziel i zwyciężaj, średnio O(n log n)
• Sortowanie przez scalanie (Merge Sort) – stabilne sortowanie, zawsze O(n log n)
• Wieże Hanoi – klasyczny problem rekurencyjny
• Przeszukiwanie grafów DFS – głębokie przeszukiwanie grafu
• Przechodzenie drzew – preorder, inorder, postorder
• Szybkie potęgowanie – obliczanie a^n w O(log n)
• Algorytm Euklidesa (NWD) – największy wspólny dzielnik

Wieże Hanoi - pełna implementacja

Wieże Hanoi to klasyczny problem rekurencyjny, sformułowany przez Édouarda Lucasa w 1883 roku. Jest doskonałym przykładem problemu, który trudno rozwiązać iteracyjnie, a rekurencyjnie jest wręcz elegancki.

Reguły gry

1. Mamy trzy słupki (A, B, C) i n krążków o różnych rozmiarach
2. Na początku wszystkie krążki są na słupku A, ułożone od największego (na dole) do najmniejszego (na górze)
3. Cel: przenieść wszystkie krążki na słupek B
4. Zasady: można przenosić tylko jeden krążek na raz, nigdy nie kładziemy większego na mniejszy

Algorytm rekurencyjny

Sprytna obserwacja: żeby przenieść n krążków z A na B, musimy:

1. Przenieść n-1 górnych krążków z A na C (używając B jako pomocniczego)
2. Przenieść największy krążek z A na B
3. Przenieść n-1 krążków z C na B (używając A jako pomocniczego)

To właśnie jest definicja rekurencyjna! Aby przenieść n krążków, musimy dwa razy przenieść n-1 krążków.

Pseudokod

funkcja hanoi(n, źródło, cel, pomocniczy)
    jeżeli n = 1 wykonuj
        wypisz("Przenieś krążek z " + źródło + " na " + cel)
    w przeciwnym razie
        hanoi(n-1, źródło, pomocniczy, cel)
        wypisz("Przenieś krążek z " + źródło + " na " + cel)
        hanoi(n-1, pomocniczy, cel, źródło)

Przykład wykonania dla n = 3

Prześledźmy wywołania krok po kroku. Wcięcia pokazują poziom rekurencji:

hanoi(3, A, B, C)                      # Cel: 3 krążki z A na B
    hanoi(2, A, C, B)                  # Podcel: 2 krążki z A na C
        hanoi(1, A, B, C)              # 1 krążek z A na B
            → Przenieś z A na B
        → Przenieś z A na C            # Środkowy krążek na C
        hanoi(1, B, C, A)              # 1 krążek z B na C
            → Przenieś z B na C
    → Przenieś z A na B                # NAJWIĘKSZY krążek na B!
    hanoi(2, C, B, A)                  # Podcel: 2 krążki z C na B
        hanoi(1, C, A, B)              # 1 krążek z C na A
            → Przenieś z C na A
        → Przenieś z C na B            # Środkowy krążek na B
        hanoi(1, A, B, C)              # 1 krążek z A na B
            → Przenieś z A na B

Wynikowa sekwencja ruchów: A→B, A→C, B→C, A→B, C→A, C→B, A→B. Razem 7 ruchów - to minimalna liczba dla 3 krążków.

Ciekawostka: minimalna liczba ruchów dla n krążków to 2^n - 1. Dla 3 krążków: 2³ - 1 = 7. Dla 64 krążków (jak w legendzie): 2^{64} - 1 ≈ 18 trylionów ruchów!

Python - Wieże Hanoi

def hanoi(n, zrodlo, cel, pomocniczy):
    if n == 1:
        print(f"Przenieś krążek z {zrodlo} na {cel}")
    else:
        hanoi(n - 1, zrodlo, pomocniczy, cel)
        print(f"Przenieś krążek z {zrodlo} na {cel}")
        hanoi(n - 1, pomocniczy, cel, zrodlo)

# Wywołanie dla 3 krążków
print("Rozwiązanie Wież Hanoi dla 3 krążków:")
hanoi(3, 'A', 'B', 'C')

C++ - Wieże Hanoi

#include <iostream>
using namespace std;

void hanoi(int n, char zrodlo, char cel, char pomocniczy) {
    if (n == 1) {
        cout << "Przenies krazek z " << zrodlo << " na " << cel << endl;
    } else {
        hanoi(n - 1, zrodlo, pomocniczy, cel);
        cout << "Przenies krazek z " << zrodlo << " na " << cel << endl;
        hanoi(n - 1, pomocniczy, cel, zrodlo);
    }
}

int main() {
    cout << "Rozwiazanie Wiez Hanoi dla 3 krazkow:" << endl;
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

Java - Wieże Hanoi

public class WiezeHanoi {
    public static void hanoi(int n, char zrodlo, char cel, char pomocniczy) {
        if (n == 1) {
            System.out.println("Przenies krazek z " + zrodlo + " na " + cel);
        } else {
            hanoi(n - 1, zrodlo, pomocniczy, cel);
            System.out.println("Przenies krazek z " + zrodlo + " na " + cel);
            hanoi(n - 1, pomocniczy, cel, zrodlo);
        }
    }

    public static void main(String[] args) {
        System.out.println("Rozwiazanie Wiez Hanoi dla 3 krazkow:");
        hanoi(3, 'A', 'B', 'C');
    }
}

Optymalizacja rekurencji - memoizacja

Jak widzieliśmy na przykładzie Fibonacciego, naiwna rekurencja może wielokrotnie obliczać te same wartości. Memoizacja (caching) to technika zapisywania wyników obliczeń, aby uniknąć powtórzeń.

Fibonacci z memoizacją

# Prosta memoizacja ręczna
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 2:
        return 1
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

# Lub elegancko z dekoratorem:
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    if n <= 2:
        return 1
    return fib_lru(n - 1) + fib_lru(n - 2)

# Teraz fib(100) działa błyskawicznie!
print(fib_lru(100))  # 354224848179261915075

Najczęściej zadawane pytania o rekurencję

Kiedy rekurencja sprawia problemy?

• Przepełnienie stosu (Stack Overflow) – gdy problem jest zbyt złożony lub brak warunku brzegowego, stos wywołań może się zapełnić. W Pythonie domyślny limit to ok. 1000 wywołań.
• Problemy z wydajnością – bez memoizacji rekurencja nieliniowa może być katastrofalnie wolna
• Błędny warunek bazowy – jeśli przypadek bazowy jest źle zdefiniowany, rekurencja może nigdy się nie zakończyć

Jak zoptymalizować algorytmy rekurencyjne?

• Memoizacja – zapisuj wyniki wcześniejszych wywołań
• Rekurencja ogonowa – pozwala kompilatorowi zoptymalizować do pętli
• Konwersja na iterację – jeśli to możliwe, zamień rekurencję na pętlę
• Programowanie dynamiczne – bardziej systematyczne podejście do problemów z powtarzającymi się podproblemami

Czym różni się rekurencja od iteracji?

Jak rozpoznać algorytm rekurencyjny?

W gotowym kodzie łatwo rozpoznasz rekurencję, znajdując wywołanie funkcji przez samą siebie. Wystarczy wyszukać (Ctrl+F) nazwę funkcji wewnątrz jej ciała. Jeśli funkcja foo zawiera w sobie wywołanie foo(...), to jest rekurencyjna.

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

Poniżej znajdziesz typowe zadanie maturalne z rekurencji wraz z pełnym rozwiązaniem. Prześledź każdy krok, aby zrozumieć, jak podchodzić do takich zadań na egzaminie.

Krok 1: Zidentyfikuj przypadek bazowy

Rekurencja musi się kiedyś zatrzymać. Zastanów się: kiedy problem jest na tyle prosty, że odpowiedź jest oczywista? Dla sumy cyfr - gdy liczba jest jednocyfrowa (lub równa 0). Wtedy suma cyfr to po prostu ta liczba.

Przypadek bazowy: n < 10  →  zwróć n

Przykład: suma_cyfr(7) = 7 (bo 7 to jednocyfrowa liczba)

Krok 2: Zdefiniuj krok rekurencyjny

Jak sprowadzić problem do mniejszego? Zauważ, że każdą liczbę można rozłożyć na: ostatnią cyfrę (n % 10) + resztę liczby (n // 10). Suma cyfr całej liczby to: ostatnia cyfra + suma cyfr reszty.

Krok rekurencyjny: suma_cyfr(n) = (n % 10) + suma_cyfr(n // 10)

Przykład: suma_cyfr(1234)
  = 4 + suma_cyfr(123)
  = 4 + (3 + suma_cyfr(12))
  = 4 + 3 + (2 + suma_cyfr(1))
  = 4 + 3 + 2 + 1
  = 10

Krok 3: Implementacja w Pythonie

def suma_cyfr(n):
    # Przypadek bazowy: jednocyfrowa liczba
    if n < 10:
        return n
    # Krok rekurencyjny: ostatnia cyfra + suma reszty
    return (n % 10) + suma_cyfr(n // 10)

# Test
print(suma_cyfr(1234))  # 10
print(suma_cyfr(9999))  # 36
print(suma_cyfr(100))   # 1

Krok 4: Implementacja w C++

#include <iostream>
using namespace std;

int suma_cyfr(int n) {
    // Przypadek bazowy
    if (n < 10) {
        return n;
    }
    // Krok rekurencyjny
    return (n % 10) + suma_cyfr(n / 10);
}

int main() {
    cout << suma_cyfr(1234) << endl;  // 10
    cout << suma_cyfr(9999) << endl;  // 36
    return 0;
}

Śledzenie wykonania krok po kroku

Dla suma_cyfr(1234) rekurencja wykonuje się następująco:

1. suma_cyfr(1234): n=1234, n>=10, więc zwracamy 4 + suma_cyfr(123)
2. suma_cyfr(123): n=123, n>=10, więc zwracamy 3 + suma_cyfr(12)
3. suma_cyfr(12): n=12, n>=10, więc zwracamy 2 + suma_cyfr(1)
4. suma_cyfr(1): n=1, n<10 → przypadek bazowy! Zwracamy 1
5. Wracamy do suma_cyfr(12): 2 + 1 = 3
6. Wracamy do suma_cyfr(123): 3 + 3 = 6
7. Wracamy do suma_cyfr(1234): 4 + 6 = 10

Podsumowanie

Rekurencja jest potężnym narzędziem, które pozwala elegancko rozwiązywać problemy o rekurencyjnej naturze. Jednak wymaga świadomego stosowania – pamiętaj o warunku bazowym, uważaj na wydajność przy rekurencji nieliniowej i rozważ memoizację lub konwersję na iterację, gdy to konieczne.

• Zawsze definiuj przypadek bazowy - to zatrzymuje rekurencję
• Każde wywołanie musi zbliżać się do przypadku bazowego - inaczej rekurencja nie zakończy się
• Rozważ złożoność - rekurencja nieliniowa może być wykładniczo wolna
• Używaj memoizacji - gdy te same wartości są obliczane wielokrotnie
• Dla prostych problemów wybierz iterację - jest szybsza i zużywa mniej pamięci

Jeśli dobrze opanujesz rekurencję, stanie się ona naturalnym sposobem myślenia o problemach algorytmicznych. A na maturze z informatyki możesz być pewien, że się przyda!

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