Temat: Na czym polega rekurencja? Rekurencyjna realizacja wybranych algorytmów klasycznych.
O rekurencji (rekursji) możemy mówić, gdy określając jakieś pojęcie odwołujemy się w definicji do niego samego. Rekurencje stosuje się w definicjach matematycznych, np. definicji liczby naturalnej:
1 jest liczba naturalną
następnik liczby naturalnej jest liczą naturalną.
W definicji liczby naturalnej następuje, bowiem odwołanie do niej samej
Aby funkcja rekurencyjna była poprawna, musi mieć ściśle zdefiniowany warunek zakończenia wywołań rekurencyjnych.
Przykład
Algorytm obliczania silni
W rekurencyjnym zapisie algorytmu silni musi pojawić się definicja silni za pomocą silni. Na przykład, aby obliczyć n!, należy obliczyć(n-1)! Itd.
Definicja
1 dla n=0
n!= (n-1)!*n dla n>0
n=4
4! = 3!*4
3!= 2!*3
2!=1!*2
1!=0!*1
Zadanie
Napisz program, który wyznaczy rekurencyjne:
silnię liczby n wprowadzonej z klawiatury
n-ty wyraz ciągu Fibonacciego (n z klawiatury)
wartość wielomianu z wykorzystaniem schematu Hornera (stopień wielomianu i argument wprowadzamy z klawiatury, a współczynniki generuje program)
n-tą potęgę liczby a (a i n wprowadzane z klawiatury)
NWD dwóch liczb naturalnych wprowadzonych z klawiatury (algorytm Euklidesa rekurencyjnie)
1