Rekurencja

Co to jest rekurencja?

Rekurencja to technika programowania, w której funkcja lub procedura wywołuje samą siebie. Algorytm oparty na takim mechanizmie nazywa się algorytmem rekurencyjnym.

Najważniejszą cechą rekurencji jest to, że problem jest rozbijany na mniejsze podproblemy tego samego typu. Każde kolejne wywołanie działa na prostszych danych, aż do osiągnięcia warunku kończącego.

Elementy algorytmu rekurencyjnego

Algorytm rekurencyjny powinien mieć:

• przypadek bazowy — warunek zakończenia rekurencji,
• wywołanie rekurencyjne — wywołanie tej samej funkcji dla prostszego przypadku.

Bez przypadku bazowego program może wykonywać się bez końca, aż do przepełnienia stosu wywołań.

Przykład

def silnia(n):
    if n == 0:
        return 1
    return n * silnia(n - 1)

Dla silnia(3) wywołania wyglądają tak:

• silnia(3) wywołuje silnia(2),
• silnia(2) wywołuje silnia(1),
• silnia(1) wywołuje silnia(0),
• silnia(0) zwraca 1.

Rekurencja a iteracja

Rekurencja często może być zastąpiona pętlą, czyli iteracją. Rekurencja bywa czytelniejsza przy problemach takich jak drzewa, silnia, ciąg Fibonacciego czy algorytmy typu „dziel i zwyciężaj”, ale może zużywać więcej pamięci przez stos wywołań.

Na egzaminie najważniejsze skojarzenie brzmi: algorytm rekurencyjny zawiera wywołanie samego siebie.