Rekurencja
Słownik kwalifikacji INF.04 - Projektowanie, programowanie i testowanie aplikacji
Rekurencja to technika programowania, w której funkcja wywołuje samą siebie. Stosuje się ją często w algorytmach, które można podzielić na mniejsze podproblemy tego samego typu.
Przykładami algorytmów często zapisywanych rekurencyjnie są:
- wyszukiwanie binarne,
- algorytm Euklidesa,
- obliczanie silni,
- generowanie liczb Fibonacciego,
- przechodzenie po drzewach.
Warunek zakończenia
Każda poprawna funkcja rekurencyjna musi mieć warunek stopu, czyli sytuację, w której funkcja przestaje wywoływać samą siebie. Bez warunku stopu program może działać bez końca albo zakończyć się błędem przepełnienia stosu.
Przykład obliczania silni:
def silnia(n):
if n == 0:
return 1
return n * silnia(n - 1)
Dla silnia(3) obliczenia wyglądają tak:
silnia(3) = 3 * silnia(2)
silnia(2) = 2 * silnia(1)
silnia(1) = 1 * silnia(0)
silnia(0) = 1
Rekurencja a iteracja
Wiele algorytmów można zapisać zarówno rekurencyjnie, jak i iteracyjnie. Wersja iteracyjna używa pętli, a wersja rekurencyjna używa kolejnych wywołań funkcji.
Rekurencja bywa czytelna, ale może zużywać więcej pamięci, ponieważ każde wywołanie funkcji trafia na stos wywołań. Dlatego w praktyce czasem wybiera się wersję iteracyjną, mimo że rekurencyjna jest prostsza do zrozumienia.