Rekurencja vs Iteracja na Maturze z Informatyki
Rekurencja (nazywana też rekursją) i iteracja to dwa fundamentalnie różne sposoby na powtarzanie operacji w programie. Iteracja to to, co znasz na co dzień: pętle 'for' i 'while'. Masz licznik, wykonujesz zadanie krok po kroku, aż licznik dojdzie do końca. Proste i przewidywalne. Rekurencja to zupełnie inna filozofia. To technika, w której funkcja... wywołuje samą siebie. Zamiast mówić 'zrób coś 10 razy', mówisz 'aby rozwiązać problem dla 10, najpierw rozwiąż go dla 9'. Aby rozwiązać dla 9, rozwiąż dla 8... i tak dalej, aż dojdziesz do najprostszego przypadku (np. dla 1), który już znasz. To jak otwieranie rosyjskich lalek Matrioszek – każda kolejna jest mniejszą wersją poprzedniej, aż dojdziesz do ostatniej, najmniejszej.
Dlaczego to ważne? Na maturze musisz rozumieć oba podejścia. Iteracja (pętle) to 90% Twojej pracy. Ale CKE uwielbia dawać zadania 'na papierze' (bez komputera), gdzie musisz prześledzić działanie *gotowej* funkcji rekurencyjnej (jak w 2025 roku) i zrozumieć, co ona robi. Czasem zadanie wprost prosi o napisanie iteracyjnego odpowiednika rekurencji. Zrozumienie, że ten sam problem (np. silnia) można rozwiązać na dwa sposoby, jest kluczowe.
Teoria
Iteracja używa pętli (stan jest trzymany w zmiennych, np. `i`, `suma`). Rekurencja używa wywołań funkcji (stan jest trzymany na 'stosie wywołań'). Każda funkcja rekurencyjna musi mieć dwie rzeczy: 1) Warunek bazowy (lub 'warunek stopu'), który przerywa wywołania. 2) Krok rekurencyjny, czyli wywołanie samej siebie, ale dla *mniejszego* problemu.
Jak to działa?
- Iteracja (Pętle `for`, `while`):
- * Jak działa: Używa pętli do powtarzania bloku kodu.
- * Stan: Stan (np. licznik `i`, suma `s`) jest jawnie przechowywany w zmiennych i aktualizowany w każdej iteracji (`i += 1`).
- * Pamięć: Bardzo wydajna pamięciowo (złożoność O(1), stała).
- * Wydajność: Zazwyczaj szybsza, bo nie ma narzutu na wielokrotne wywoływanie funkcji.
- * Ryzyko: Pętla nieskończona (np. `while True` bez `break` lub zapomnienie o `i += 1`).
- Rekurencja (Funkcje wywołujące same siebie):
- * Jak działa: Dzieli problem na mniejsze podproblemy tego samego typu.
- * Stan: Stan jest niejawnie przechowywany na stosie wywołań. Każde wywołanie ma własne zmienne lokalne.
- * Pamięć: Zużywa pamięć proporcjonalną do głębokości rekursji (złożoność O(n)).
- * Wydajność: Zazwyczaj wolniejsza (narzut na wywołanie funkcji). Niektóre implementacje (np. naiwny Fibonacci) są *dramatycznie* wolne (O(2^n)).
- * Ryzyko: Przepełnienie stosu (`RecursionError` / `Stack Overflow`) jeśli warunek bazowy jest zły lub rekurencja jest za głęboka.
Złożoność: Złożoność zależy od problemu. Dla silni: obie wersje mają złożoność czasową O(n). Ale iteracja ma O(1) pamięci, a rekurencja O(n) pamięci (na stosie). Dla Fibonacciego: iteracja ma O(n) czasu i O(1) pamięci. Naiwna rekurencja ma O(2^n) czasu, co jest katastrofą.
Implementacja
Silnia - Wersja Iteracyjna (pętla FOR)
Pythondef silnia_iter(n):
wynik = 1
# Pętla od 1 do n włącznie
for i in range(1, n + 1):
wynik = wynik * i
return wynik
print(f"Silnia 5 (iter): {silnia_iter(5)}") # 120Klasyczny przykład iteracji. Tworzymy zmienną 'wynik'. Pętla 'for' mnoży 'wynik' przez kolejne liczby (1, 2, 3, 4, 5). Proste, szybkie i wydajne pamięciowo.
Silnia - Wersja Rekurencyjna
Pythondef silnia_rek(n):
# 1. Warunek bazowy (stopu)
if n == 0 or n == 1:
return 1
# 2. Krok rekurencyjny
else:
return n * silnia_rek(n - 1)
print(f"Silnia 5 (rek): {silnia_rek(5)}") # 120To jest definicja rekurencyjna. Silnia(5) to `5 * silnia_rek(4)`. Silnia_rek(4) to `4 * silnia_rek(3)`... aż do `silnia_rek(1)`, które zwraca 1. Kod jest bardzo elegancki i bliski definicji matematycznej.
Fibonacci - Wersja Iteracyjna (SZYBKA)
Pythondef fib_iter(n):
if n <= 1:
return n
a, b = 0, 1 # Dwa poprzednie wyrazy
for _ in range(n - 1):
a, b = b, a + b
return b
print(f"Fibonacci 10 (iter): {fib_iter(10)}") # 55
print(f"Fibonacci 40 (iter): {fib_iter(40)}") # 102334155Wersja iteracyjna jest bardzo szybka (O(n)). Przechowujemy tylko dwa ostatnie wyrazy (`a` i `b`) i w pętli obliczamy kolejny, zamieniając je miejscami. Obliczenie F(40) jest natychmiastowe.
Fibonacci - Wersja Rekurencyjna (Naiwna, BARDZO WOLNA)
Pythondef fib_rek(n):
if n <= 1:
return n
else:
# Oblicza te same wartości wielokrotnie!
return fib_rek(n - 1) + fib_rek(n - 2)
print(f"Fibonacci 10 (rek): {fib_rek(10)}") # 55
# print(f"Fibonacci 40 (rek): {fib_rek(40)}") # NIE URUCHAMIAJ - potrwa bardzo długo!To jest zły przykład użycia rekurencji. Funkcja ma złożoność O(2^n), bo aby policzyć `fib_rek(5)`, liczy `fib_rek(4)` i `fib_rek(3)`. Aby policzyć `fib_rek(4)`, znów liczy `fib_rek(3)` i `fib_rek(2)`. Ta sama wartość `fib_rek(3)` jest liczona dwa razy! Dla F(40) powoduje to miliardy zbędnych operacji.
Przykładowe Zadania Maturalne
Napisz dwie funkcje (jedną iteracyjną, drugą rekurencyjną), które obliczają sumę cyfr podanej liczby naturalnej 'n'. Na przykład dla n = 123, obie funkcje powinny zwrócić 6 (bo 1+2+3=6).
Wskazówka: Iteracja: Użyj pętli 'while n > 0'. W każdej iteracji bierz ostatnią cyfrę (n % 10) i dodawaj do sumy, a następnie 'skracaj' liczbę (n = n // 10). Rekurencja: Warunek bazowy to 'n == 0'. Krok rekurencyjny to 'ostatnia_cyfra + suma_cyfr(reszta_liczby)', czyli `(n % 10) + suma_cyfr(n // 10)`.
Pokaż szkic rozwiązania
# Wersja iteracyjna
def suma_iter(n):
suma = 0
while n > 0:
suma += n % 10
n = n // 10
return suma
# Wersja rekurencyjna
def suma_rek(n):
if n == 0:
return 0
else:
return (n % 10) + suma_rek(n // 10)Dana jest rekurencyjna funkcja 'przestaw(n)' [tu znajduje się jej pseudokod]. W postaci pseudokodu lub w wybranym języku programowania napisz nierekurencyjną funkcję 'przestaw2', która dla danej nieujemnej liczby całkowitej n da taką samą wartość jak 'przestaw(n)'.
Wskazówka: Przeanalizuj, co robi funkcja rekurencyjna. Bierze ona liczbę 'n', obcina jej ostatnie dwie cyfry (`n div 100`) i wywołuje siebie dla tej obciętej liczby. Wynik mnoży przez 100 i dodaje dwie ostatnie cyfry w odwróconej kolejności. Twoja funkcja iteracyjna musi robić to samo, ale 'od dołu do góry'. Użyj pętli 'while n > 0' i buduj wynik 'w' od końca, używając potęgi 10 (np. zmiennej 'mnoznik').
Pokaż szkic rozwiązania
1. Zdefiniuj funkcję `przestaw2(n)`. 2. Zainicjuj wynik `w = 0`. 3. Zainicjuj mnożnik potęgi 10: `mnoznik = 1`. 4. Rozpocznij pętlę `while n > 0`. 5. W pętli pobierz dwie ostatnie cyfry: `a = (n // 10) % 10` (cyfra dziesiątek) i `b = n % 10` (cyfra jedności). 6. Obetnij `n` o dwie cyfry: `n = n // 100`. 7. Oblicz 'zamienioną' parę: `para = b * 10 + a` (chyba że to ostatnie cyfry, wtedy obsłuż `a=0` lub `b=0` zgodnie z treścią zadania). 8. Dodaj tę parę do wyniku na odpowiedniej pozycji: `w = w + para * mnoznik`. 9. Zwiększ mnożnik: `mnoznik = mnoznik * 100`. 10. Zwróć `w` (z uwzględnieniem specjalnych warunków brzegowych dla `a` i `b` z treści zadania).
Częste Błędy
❌ Rekurencja: Brak warunku bazowego (stopu)
To najgorszy błąd. Jeśli funkcja rekurencyjna nie ma warunku, który ją zatrzymuje (np. `if n == 0: return 1`), będzie wywoływać samą siebie w nieskończoność.
Poprawka: Zawsze zacznij pisać funkcję rekurencyjną od `if warunek_bazowy: ...`.
❌ Rekurencja: Przepełnienie stosu (Stack Overflow)
Dzieje się tak, gdy rekurencja jest za głęboka (np. wywołujesz `silnia_rek(5000)`). Python ma limit wywołań (zwykle 1000). To pokazuje, że rekurencja nie nadaje się do *każdego* problemu, który można rozwiązać pętlą.
Poprawka: Jeśli spodziewasz się dużej liczby iteracji (tysiące), użyj iteracji (pętli) zamiast rekurencji.
❌ Rekurencja: Zapomnienie o `return`
Uczeń pisze `return n * silnia_rek(n-1)` co jest super. Ale dla Fibonacciego pisze `fib_rek(n-1) + fib_rek(n-2)` zapominając o `return` przed tym. Funkcja nic nie zwróci.
Poprawka: Krok rekurencyjny *prawie zawsze* musi zwracać (`return`) wynik swojego obliczenia.
❌ Iteracja: Nieskończona pętla `while`
Odpowiednik braku warunku bazowego. Piszesz `i = 0; while i < 10: print(i)`. Zapominasz o `i += 1`. `i` zawsze będzie 0, pętla nigdy się nie skończy.
Poprawka: Zawsze upewnij się, że wewnątrz pętli `while` zmienna warunkowa jest modyfikowana i dąży do przerwania pętli.
❌ Naiwna rekurencja dla Fibonacciego
Użycie `fib(n-1) + fib(n-2)` to klasyczna pułapka. To jest złożoność wykładnicza O(2^n). Na maturze taki kod nie przejdzie testów wydajnościowych.
Poprawka: Ciąg Fibonacciego *zawsze* implementuj iteracyjnie (z pętlą i dwiema zmiennymi `a` i `b`).
Kluczowe Wnioski
- Iteracja (pętle `for`, `while`) jest zazwyczaj szybsza i zużywa mniej pamięci (O(1)).
- Rekurencja (funkcja wywołująca siebie) jest często bardziej elegancka i krótsza, ale zużywa pamięć na stosie (O(n)).
- Każda funkcja rekurencyjna musi mieć warunek bazowy (stopu).
- Każde wywołanie rekurencyjne musi zmniejszać problem (np. `n-1`), aby dążyć do warunku bazowego.
- Na maturze iteracja jest bezpieczniejszym i preferowanym wyborem do pisania kodu (np. silnia, Fibonacci, NWD).
- Na maturze musisz umieć *analizować* gotowy kod rekurencyjny (jak w zadaniu 1. z Matury 2025).
- Uważaj na pułapkę wydajnościową naiwnej rekurencji dla Fibonacciego (złożoność O(2^n)).
Najczęściej Zadawane Pytania
❓ Co jest szybsze: rekurencja czy iteracja?
Prawie zawsze iteracja jest szybsza. Wywołanie funkcji (co robi rekurencja) ma swój 'koszt' (stworzenie ramki stosu, skok), podczas gdy pętla to prosty skok procesora. Dla prostych zadań (silnia, NWD) iteracja wygrywa.
❓ Co to jest przepełnienie stosu (Stack Overflow)?
To błąd, który występuje, gdy rekurencja jest zbyt głęboka. Każde wywołanie funkcji 'odkłada' na stosie swój stan. Jeśli wywołań jest za dużo (np. 1000 lub więcej), stos się 'przepełnia', bo brakuje mu pamięci. Iteracja nie ma tego problemu.
❓ Czy muszę umieć oba na maturę?
Musisz umieć *implementować* iterację (pętle). Musisz umieć *rozumieć i analizować* rekurencję. Umiejętność napisania prostej rekurencji (np. dla NWD) jest dużym plusem.
❓ Kiedy rekurencja jest lepsza od iteracji?
Rekurencja jest naturalnym wyborem dla problemów, które same w sobie są rekurencyjne. Np. algorytmy 'Dziel i Zwyciężaj' (jak Quicksort, Mergesort) lub algorytmy na strukturach drzewiastych. Kod iteracyjny byłby dla nich o wiele dłuższy i bardziej skomplikowany.
Chcesz opanować wszystkie tematy maturalne?
Dołącz do kursu i zyskaj dostęp do interaktywnych lekcji, edytora kodu i setek zadań.