Rekurencja — lekcja z rozpisywaniem kolejnych wywołań

Funkcja rekurencyjna wywołuje samą siebie na mniejszym fragmencie problemu — tak jak lustro ustawione naprzeciw lustra. Rekurencja pozwala krótko zapisać algorytmy, które iteracyjnie byłyby długie, ale jest trudna dla początkujących, bo trzeba śledzić wiele jednoczesnych wywołań. Dlatego lekcja zaczyna się od rozpisywania wywołań na kartce, a dopiero potem przechodzi do programów.

Scenariusz jest przeznaczony na 45 minut dla klasy znającej funkcje i instrukcje warunkowe w Pythonie — na przykład po lekcjach o funkcjach i algorytmie Euklidesa.

Przygotowanie stanowisk

Potrzebny jest Python 3 i edytor lub IDLE. Rozpakuj pakiet z sekcji materiałów do osobnego folderu i uruchamiaj skrypty z tego folderu. Program uruchomisz przez Run → Run Module albo poleceniem python start.py, python3 start.py lub py start.py.

Cele i plan lekcji

Po zajęciach uczeń potrafi:

• wskazać w funkcji rekurencyjnej warunek zakończenia i krok rekurencyjny;
• rozpisać na kartce kolejne wywołania silnia(4);
• zapisać rekurencyjnie sumę cyfr, ciąg Fibonacciego, potęgę i odwracanie napisu;
• wyjaśnić, dlaczego brak warunku zakończenia kończy się błędem RecursionError i dlaczego rekurencyjny Fibonacci jest wolny.

Anatomia funkcji rekurencyjnej

Każda poprawna funkcja rekurencyjna ma dwie części: warunek zakończenia (przypadek podstawowy, dla którego znamy wynik) i krok rekurencyjny (wywołanie dla mniejszego problemu, które w końcu doprowadzi do przypadku podstawowego). Dla silni: 0! = 1! = 1 (podstawa), n! = n · (n−1)! (krok). Wywołanie silnia(4) rozpisujemy tak:

silnia(4) = 4 * silnia(3)
          = 4 * (3 * silnia(2))
          = 4 * (3 * (2 * silnia(1)))
          = 4 * (3 * (2 * 1))  = 24

Python pamięta wszystkie rozpoczęte wywołania na stosie. Gdy brakuje warunku zakończenia, wywołania nie kończą się, a po około tysiącu Python przerywa program błędem RecursionError.

Ciąg Fibonacciego (fib(n) = fib(n−1) + fib(n−2)) pokazuje drugą stronę rekurencji: proste rozwiązanie wywołuje się bardzo wiele razy dla tych samych argumentów — fib(10) oblicza się w 177 wywołaniach, a fib(30) już w ponad 2 milionach. Dlatego w praktyce dla takich zadań stosuje się pętlę albo zapamiętywanie wyników.

Zadania

Zadanie 1. Silnia i suma cyfr. Napisz rekurencyjnie silnia(n) i suma_cyfr(n) (resztą z dzielenia przez 10 i dzieleniem całkowitym). Sprawdź silnię z 0, 1, 5 i 10 oraz sumę cyfr 7, 2026 i 999.

Zadanie 2. Fibonacci. Napisz fib(n) i wypisz pierwsze 11 wyrazów ciągu. Policz, ile razy wywołana zostanie funkcja przy obliczaniu fib(10) (licznik globalny).

Zadanie 3. Potęga, napis i błąd. Napisz potega(a, n) i odwroc(napis) rekurencyjnie. Sprawdź potega(2, 10), potega(5, 0), potega(3, 4) oraz odwróć rekurencja, a i pusty napis. Wywołaj funkcję bez warunku zakończenia i obsłuż RecursionError.

Dla chętnych: napisz rekurencyjnie suma_listy(lista) i sprawdź ją dla [1, 2, 3, 4] oraz pustej listy.

Rozwiązanie i wyniki

def silnia(n):
    if n <= 1:
        return 1
    return n * silnia(n - 1)


def suma_cyfr(n):
    if n < 10:
        return n
    return n % 10 + suma_cyfr(n // 10)


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


wywolania = 0


def fib_licznik(n):
    global wywolania
    wywolania = wywolania + 1
    if n < 2:
        return n
    return fib_licznik(n - 1) + fib_licznik(n - 2)


def potega(a, n):
    if n == 0:
        return 1
    return a * potega(a, n - 1)


# Zadanie 1
print(silnia(0), silnia(1), silnia(5), silnia(10))
print(suma_cyfr(7), suma_cyfr(2026), suma_cyfr(999))

# Zadanie 2
print([fib(i) for i in range(11)])
fib_licznik(10)
print("Wywolan fib(10):", wywolania)

# Zadanie 3
print(potega(2, 10), potega(5, 0), potega(3, 4))
def odwroc(napis):
    if len(napis) <= 1:
        return napis
    return odwroc(napis[1:]) + napis[0]


print(odwroc("rekurencja"), odwroc("a"), odwroc(""))
try:
    silnia_zla = lambda n: n * silnia_zla(n - 1)
    silnia_zla(5)
except RecursionError:
    print("RecursionError: brak warunku zakonczenia")

Program wypisze:

1 1 120 3628800
7 10 27
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Wywolan fib(10): 177
1024 1 81
ajcneruker a 
RecursionError: brak warunku zakonczenia

Silnia z 10 to 3 628 800. Obliczenie fib(10) wymaga 177 wywołań, choć wynik to tylko 55 — to ilustracja kosztu prostej rekurencji. Zadanie dla chętnych (rozszerzenie.py) wypisuje:

10 0

Typowe błędy

Pytania kontrolne i punktacja

1. Jakie dwie części ma funkcja rekurencyjna?
2. Ile wynosi silnia(5) i jak to rozpisać?
3. Dlaczego rekurencyjny fib(30) jest wolny?

Odpowiedzi: Warunek zakończenia i krok rekurencyjny. 120: 5 · 4 · 3 · 2 · 1. Bo te same wartości są obliczane wiele razy, a liczba wywołań rośnie wykładniczo.

Proponowana punktacja (razem 10 punktów): zadanie 1 — silnia 2 pkt, suma_cyfr 2 pkt; zadanie 2 — fib 2 pkt, licznik wywołań 1 pkt; zadanie 3 — potega i odwroc 2 pkt, obsługa RecursionError 1 pkt. Zadanie dla chętnych nie jest wymagane do pełnej oceny.

Materiały do pobrania

• Pakiet Informatyka: materiały do lekcji, rozwiązanie i karta pracy
• Karta pracy ucznia — otwórz i wydrukuj

Rozpakuj ZIP przed otwarciem plików. Materiały są dostępne bez logowania; publiczne rozwiązanie służy nauce i samodzielnemu sprawdzeniu, a nie poufnemu sprawdzianowi.

Co dalej?

Następny krok to zapamiętywanie wyników (memoizacja), przeszukiwanie drzew i algorytmy typu „dziel i zwyciężaj”. Ten materiał rozwija dział o algorytmach w kursie Informatyka w TablicaPro, gdzie znajdziesz prezentacje, ćwiczenia i testy do prowadzenia lekcji.

Źródła techniczne: rekurencja w Wikipedii oraz funkcje w tutorialu Pythona. Zobacz też lekcję o liczbach pierwszych.