Rekurencja i Jej Rozwijanie
Zadania rekurencyjne wracają na maturze rozszerzonej co roku. Jak odczytać wzór, rozwinąć wywołania krok po kroku i oszacować liczbę operacji.
1. Każda rekurencja ma dwie części
Niezależnie od tego, czy patrzysz na silnię, Fibonacciego czy Euklidesa, rekurencja zawsze składa się z tych samych dwóch elementów. Jeśli zabraknie któregokolwiek, program zapętla się w nieskończoność.
- Warunek początkowy — sytuacja, w której funkcja zwraca wynik bez wywoływania siebie.
- Wywołanie rekurencyjne — krok, który zbliża argument do warunku początkowego.
def silnia(n):
if n <= 1: # warunek początkowy
return 1
return n * silnia(n - 1) # krok rekurencyjny2. Rozwijanie wywołań na kartce
Najczęstsze polecenie brzmi: „podaj wartość zwróconą przez wywołanie" albo „ile razy wykona się instrukcja". Trzeba wtedy rozpisać drzewo wywołań. Rób to schodkowo, od góry w dół, i dopiero potem zwijaj wyniki z powrotem.
Wyniki zwijaj dopiero po dojściu do warunku początkowego. Próba liczenia „w locie", w trakcie schodzenia w dół, to najczęstsze źródło błędów w tym zadaniu.
3. Fibonacci i pułapka wykładnicza
Naiwny Fibonacci wywołuje się dwa razy w każdym kroku, przez co liczba wywołań rośnie wykładniczo — złożoność rzędu . To ulubiony materiał na pytanie „dlaczego program działa wolno".
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2) # dwa wywolania - drzewo sie rozgaleziaRozwiązaniem jest zapamiętywanie wyników albo wersja iteracyjna, która schodzi do . Jeśli w zadaniu pada słowo „usprawnij", chodzi właśnie o to.
4. Co sprawdza egzaminator
- Brak warunku początkowego — program nigdy się nie zatrzyma, a zadanie idzie na zero.
- Krok, który nie zbliża do końca. Wywołanie
f(n)wewnątrzf(n)to ta sama pętla bez końca. - Mylenie liczby wywołań z wynikiem. Czytaj uważnie, o co pytają.
- Nieuwzględnienie wywołania początkowego przy zliczaniu — to klasyczna pomyłka o jeden.
Nadal czujesz się niepewnie?
To tylko jeden z pewniaków. Na kursie przechodzimy przez nie wszystkie, krok po kroku, aż poczujesz ten spokój.
Pomóżcie mi zdać maturę!