Reklama
Wizyt
Dzisiaj: 31Wszystkich: 53977

Rekurencyjna realizacja wybranych algorytmów

Informatyka » zakres rozszerzony » 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

 

 

 

 

Reklama