Rekurencja
Definicje rekurencyjne, liczba wywołań, drzewo wywołań, przejście na iterację, memoizacja.
Teoria, wzory i przykłady
Jak działa rekurencja
Funkcja rekurencyjna wywołuje samą siebie dla mniejszego problemu i ma warunek zakończenia (przypadek bazowy).
Śledzenie wywołań
Rozpisuj wywołania krok po kroku, wpisując argumenty. Przykład funkcji z arkusza CKE 2026:
: kolejne wywołania , , — 3 wywołania rekurencyjne, wynik .
Obserwacja: drugi argument jest za każdym razem (prawie) dzielony przez 2 — liczba wywołań ma rząd . Dla wywołań jest ; dla (same nieparzyste kroki) wywołań jest .
Wzór: ta funkcja oblicza po prostu iloczyn, (to mnożenie „rosyjskich chłopów”: dla parzystego podwajamy i dzielimy przez 2, dla nieparzystego dodajemy ). Sprawdź: oraz . W zadaniach maturalnych wzór najłatwiej zauważyć, rozpisując kilka małych przykładów.
Rekurencja a iteracja
Każdą rekurencję ogonową można zamienić na pętlę. Rekurencję wielokrotną (Fibonacci) warto przyspieszyć memoizacją (zapamiętywaniem wyników) — z wykładniczej do liniowej .
def fib(n, pamiec={}):
if n <= 1:
return n
if n not in pamiec:
pamiec[n] = fib(n - 1) + fib(n - 2)
return pamiec[n]
Wieże Hanoi
ruchów.
Typowe błędy
- Brak warunku zakończenia ⇒ nieskończona rekurencja.
- Pomylenie „liczby wywołań rekurencyjnych” z „wartością funkcji”.
Średnie zadania
Rekurencja. Dana jest zdefiniowana rekurencyjnie funkcja , gdzie i są dodatnimi liczbami całkowitymi:
Obliczenie wprost z definicji wymaga trzech wywołań rekurencyjnych: , , , bo .
Podaj liczbę wywołań rekurencyjnych funkcji oraz wypisz wywołania rekurencyjne (w ostatnim wierszu podaj tylko liczbę wywołań) dla:
| (przykład: 3 wywołania) | |
Dla funkcji z zadania 1.1 podaj wartości:
| ? | ||
| ? |
(Wynik możesz zapisać z użyciem mnożenia i potęgowania.)
Funkcja rekurencyjna. Dana jest funkcja przestaw, której parametrem jest nieujemna liczba całkowita:
przestaw(n):
r ← n mod 100
a ← r div 10
b ← r mod 10
n ← n div 100
jeżeli n > 0
w ← a + 10*b + 100*przestaw(n)
w przeciwnym razie
jeżeli a > 0
w ← a + 10*b
w przeciwnym razie
w ← b
wynikiem jest w
(mod — reszta z dzielenia, div — dzielenie całkowite.) Uzupełnij tabelę: wynik przestaw(n) oraz liczba wywołań funkcji przestaw łącznie z pierwszym wywołaniem.
| wynik | liczba wywołań | |
|---|---|---|
| 316498 | 134689 | 3 |
| 43657688 | ? | ? |
| 154005710 | ? | ? |
| 998877665544321 | ? | ? |
Niech będzie liczbą -cyfrową, gdzie . Liczba wywołań funkcji przestaw (z zadania 1.1) w zależności od jest równa — oceń prawdziwość zapisów:
Trudne zadania
Uzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji dla każdej wartości (drugiego argumentu; pierwszy jest nieistotny). W trzeciej kolumnie podaj wyrażenie, którego wartość jest równa drugiemu argumentowi funkcji w -tym wywołaniu rekurencyjnym (dla liczba wywołań).
| liczba wywołań | drugi argument w -tym wywołaniu | |
|---|---|---|
| (lub ) | ||
| ? | ? | |
| ? | ? |
gdzie jest pewną liczbą całkowitą dodatnią większą od 2.
W pseudokodzie lub w wybranym języku programowania napisz nierekurencyjną funkcję przestaw2, która dla danej nieujemnej liczby całkowitej da taką samą wartość jak przestaw(n).
Uwaga: algorytm może używać wyłącznie zmiennych przechowujących liczby całkowite i operować tylko na liczbach całkowitych; dozwolone są operacje arytmetyczne (w tym dzielenie całkowite i reszta), porównania, instrukcje sterujące, przypisania i własne funkcje z tych operacji. Zabronione są funkcje wbudowane oraz funkcja przestaw.