Rekurencyjna realizacja wybranych algorytmów

Rekurencja

Rekurencja jest techniką programowania wykorzystującą funkcje, które wywołują same siebie. Jest to alternatywny dla pętli sposób powtarzania pewnych czynności, gdzie kolejny etap jest podzadaniem poprzedniego. Przy redukcji problemu wymagany jest wyraźnie określony warunek zakończenia (przypadek podstawowy).

Rekurencyjne obliczanie silni

Typowym przykładem rekurencji jest definicja silnia:

Wartość silni dla 0 jest przypadkiem elementarnym.

Sposób obliczania wartości 4! można przedstawić następująco:

Program obliczający silnię z liczby n sposobem rekurencyjnym

Rekurencyjne obliczanie NWD (algorytmu Euklidesa)

Rekurencyjny sposób na obliczenie NWD można zapisać wzorem:

Program obliczający NWD dwóch liczb sposobem rekurencyjnym

Rekurencyjne obliczanie elementów ciągu Fibonacciego

Rekurencyjny wzór na wyznaczanie elementów ciągu Fibonacciego ma postać:

 
Program obliczający elementy ciągu Fibonacciego sposobem rekurencyjnym

Mierzenie czasu wykonania programu