Rekurencja — moc samoodwołania
Wstęp do działu
Spotkałeś już rekurencję trzy razy — u Euklidesa (4.2), przy Fibonaccim (4.3) i w scalaniu (6.6) — za każdym razem jak epizodycznego gościa. Teraz dostaje główną rolę, bo zasługuje na nią jak żaden inny pomysł w informatyce. Rekurencja to funkcja, która wywołuje samą siebie — i choć brzmi to jak przepis na nieskończoną pętlę albo filozoficzny żart, jest jednym z najpotężniejszych narzędzi rozwiązywania problemów, jakie wymyślono.
Sekret w tym, że rekurencja dosłownie zapisuje myślenie z jednostki 1.4: „rozwiąż problem tą samą metodą zastosowaną do jego mniejszej kopii". Gdy pomysł jest z natury samopodobny — a zaskakująco wiele jest — rekurencyjny kod bywa krótszy i jaśniejszy od jakiejkolwiek pętli. W tym dziale zrozumiesz mechanizm od podszewki (co się naprawdę dzieje w pamięci, gdy funkcja woła siebie), nauczysz się rozstrzygać „rekurencja czy iteracja", a w rozszerzeniu narysujesz fraktale — figury, w których samopodobieństwo widać gołym okiem — i policzysz rzeczy, które inaczej policzyć się nie da: miejsca zerowe funkcji, pierwiastki, całki przez losowanie.
Mapa pojęć działu
REKURENCJA — funkcja woła samą siebie
|
┌─────────────────────┴──────────────────────┐
MECHANIZM ZASTOSOWANIA
przypadek bazowy (stop!) [R] dziel i zwyciężaj
krok rekurencyjny (mniejszy!) [R] fraktale (samopodobne!)
stos wywołań [R] miejsca zerowe (połowienie)
| [R] pierwiastek (Newton)
REKURENCJA vs ITERACJA
(kształt drzewa wywołań:
łańcuch — tanio, drzewo — drogo)
Jednostki w tym dziale
- 7.1 Funkcja, która woła samą siebie — mechanizm i stos
- 7.2 Rekurencja czy iteracja? — dwa oblicza tego samego
- 7.3 Dziel i zwyciężaj — rama metody (rozszerzenie)
- 7.4 Fraktale — samopodobieństwo na ekranie (rozszerzenie)
- 7.5 Miejsca zerowe metodą połowienia (rozszerzenie)
- 7.6 Przybliżony pierwiastek — Babilon i Newton (rozszerzenie)