Czego się nauczysz
Zapiszesz algorytm Euklidesa i szybkie potęgowanie jako funkcje rekurencyjne i zobaczysz, jak płytko schodzą na stosie wywołań.
Po co ci to na maturze
W arkuszach pojawiają się rekurencyjne wersje znanych algorytmów, np. NWD albo potęgowania, z pytaniem o wynik albo o liczbę wywołań. Ta lekcja pokazuje, jak takie funkcje śledzić.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Dwa wzory rekurencyjneWynik dla dużych liczb zależy od wyniku dla mniejszych. Euklides ma taki wzór od początku, potęgę trzeba wyprowadzić.
- 1.2NWD rekurencyjnieKażde wywołanie odkłada ramkę na stos, a wynik wraca w górę bez zmian.
- 1.3Szybkie potęgowanie rekurencyjnieJedno wywołanie dla połowy wykładnika i wynik do kwadratu. Dwa wywołania psują wszystko.
- 1.4Rekurencja czy pętlaKażde wywołanie zajmuje miejsce na stosie. Python pozwala na około tysiąc naraz.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.