BLOK 03 · 2 godz. Rekurencja Stos wywołań Fraktale

Rekurencja vs Iteracja & Fraktale

Informatyka Rozszerzona · Klasa 4 · Semestr I · Blok 03/30

1. Czym jest rekurencja?

Funkcja jest rekurencyjna, gdy wywołuje samą siebie w celu rozwiązania mniejszej wersji tego samego problemu. Każda poprawna funkcja rekurencyjna musi mieć dwa elementy:

Warunek stopu (przypadek bazowy) — sytuacja, w której funkcja nie wywołuje już samej siebie, tylko zwraca wynik wprost.
Krok rekurencyjny — funkcja wywołuje samą siebie dla mniejszego / prostszego podproblemu, zbliżając się do warunku stopu.

Brak warunku stopu = przepełnienie stosu

Jeśli funkcja rekurencyjna nigdy nie osiąga przypadku bazowego, program zgłosi błąd RecursionError: maximum recursion depth exceeded. To najczęstszy błąd początkujących.

2. Silnia — rekurencja vs iteracja

Wersja rekurencyjna

def silnia_rek(n):
    if n == 0: # przypadek bazowy
        return 1
    return n * silnia_rek(n - 1) # krok rekurencyjny

Wersja iteracyjna

def silnia_iter(n):
    wynik = 1
    for i in range(1, n + 1):
        wynik *= i
    return wynik

Wizualizacja stosu wywołań dla silnia_rek(4)

Każde wywołanie funkcji odkłada na stos wywołań nową "ramkę", która czeka, aż wywołanie zagnieżdżone zwróci wynik:

silnia_rek(4) → czeka na silnia_rek(3), potem zwróci 4 × wynik

silnia_rek(3) → czeka na silnia_rek(2), potem zwróci 3 × wynik

silnia_rek(2) → czeka na silnia_rek(1), potem zwróci 2 × wynik

silnia_rek(1) → czeka na silnia_rek(0), potem zwróci 1 × wynik

silnia_rek(0) → przypadek bazowy, zwraca 1 (stos zaczyna się "zwijać")

Kryterium	Rekurencja	Iteracja
Czytelność dla problemów "z natury rekurencyjnych"	Zwykle wyższa (drzewa, fraktale, przeszukiwanie grafów)	Może wymagać dodatkowych struktur (np. własnego stosu)
Zużycie pamięci	Wyższe — każde wywołanie zajmuje ramkę na stosie	Stałe — jedna zmienna licznika
Ryzyko błędu	Przepełnienie stosu przy braku/złym warunku stopu	Pętla nieskończona przy błędnym warunku
Szybkość	Zwykle wolniejsza (narzut wywołań funkcji)	Zwykle szybsza

3. Fraktale — rekurencja w praktyce

Fraktal to figura, której fragment wygląda podobnie do całości — idealny przykład zastosowania rekurencji. Klasyczny przykład: drzewo fraktalne — gałąź rozgałęzia się na dwie mniejsze gałęzie, każda z nich znowu na dwie, aż do osiągnięcia minimalnej długości (warunek stopu).

# Pseudokod rysowania drzewa fraktalnego (np. z modułem turtle)
def rysuj_galaz(dlugosc):
    if dlugosc < 5: # przypadek bazowy — gałąź za krótka
        return
    narysuj_linie(dlugosc)
    skret(20)
    rysuj_galaz(dlugosc * 0.7) # prawa gałąź
    skret(-40)
    rysuj_galaz(dlugosc * 0.7) # lewa gałąź
    skret(20) # powrót do pierwotnego kierunku

Inne znane fraktale rekurencyjne

Trójkąt Sierpińskiego — trójkąt dzielony rekurencyjnie na 3 mniejsze trójkąty w narożnikach. Płatek Kocha — każdy odcinek zastępowany łamaną w kształcie "ząbka". Oba budowane są dokładnie tą samą techniką: funkcja rekurencyjna z warunkiem stopu opartym na głębokości rekursji lub minimalnym rozmiarze.

4. Ćwiczenia praktyczne

Ćwiczenie 1 — Ciąg Fibonacciego rekurencyjnie

Napisz funkcję rekurencyjną fib(n) zwracającą n-ty wyraz ciągu Fibonacciego (fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)). Następnie odpowiedz: dlaczego dla n=35 program zauważalnie zwalnia?

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

Ta wersja ma złożoność O(2ⁿ) — te same podproblemy (np. fib(30)) liczone są wielokrotnie, bo funkcja nie zapamiętuje wcześniej obliczonych wyników. To problem, który rozwiążemy metodą programowania dynamicznego w Bloku 15.

Ćwiczenie 2 — Suma cyfr liczby (rekurencyjnie)

Napisz funkcję suma_cyfr(n), która rekurencyjnie sumuje cyfry liczby naturalnej n (np. suma_cyfr(1234) = 10).

def suma_cyfr(n):
    if n < 10: # przypadek bazowy — jedna cyfra
        return n
    return n % 10 + suma_cyfr(n // 10)

5. Sprawdź wiedzę

1. Co się stanie, jeśli funkcja rekurencyjna nie ma poprawnego warunku stopu?

Program zwróci 0 Program zgłosi błąd przepełnienia stosu Program zadziała wolniej, ale poprawnie

2. Co jest odkładane na stos wywołań przy każdym wywołaniu funkcji rekurencyjnej?

Cała treść programu Ramka wywołania (parametry, stan lokalny, miejsce powrotu) Kopia wszystkich zmiennych globalnych

3. Co czyni figurę fraktalem?

Ma dokładnie 3 boki Fragment figury wygląda podobnie do całości (samopodobieństwo) Jest rysowana wyłącznie w kolorze zielonym

6. Podsumowanie bloku

Rozumiem różnicę między warunkiem stopu a krokiem rekurencyjnym.
Potrafię przekształcić prosty algorytm iteracyjny na rekurencyjny i odwrotnie.
Rozumiem, jak działa stos wywołań podczas wykonywania funkcji rekurencyjnej.
Napisałem funkcję rekurencyjną generującą prosty fraktal (drzewo, trójkąt Sierpińskiego).

← Blok 02: Złożoność obliczeniowa Blok 04: Dziel i zwyciężaj →