Rekurencja – odwołanie do samej siebie
Z rekurencją mamy do czynienia gdy określając jakieś pojęcie, odwołujemy się w definicji do niego samego.
- rekurencję stosuje się w definicjach matematycznych np w definicji liczby naturalnej
a) 1 jest liczbą naturalną
b) następnik liczby naturalnej jest liczbą naturalną
w definicji liczby naturalnej następuje zatem odwołanie do niej samej - efekt odbicia w lustrze nakierowanego na inne lustro
- reguła: każdy ojciec jest starszy od swojego syna; każdy ojciec jest czyimś synem
– stan początkowy: jestem 22-letnim mężczyzną
– teza: ojciec ojca mojego ojca jest starszy ode mnie
– dowód: mój ojciec jest starszy ode mnie
mój ojciec jest czyimś synem
ojciec mojego ojca jest starszy od mojego ojca
ojciec mojego ojca jest czyimś synem
itd.
W INFORMATYCE REKURENCJA JEST SZCZEGÓLNYM RODZAJEM POWTÓRZEŃ BEZ KONIECZNOŚCI STOSOWANIA PĘTLI
- Rekurencyjna definicja silni liczby naturalnej n -> program
n! = 1 dla n=0
n! = (n-1)!*n dla n>0
czyli
3!=2!*3
2!=1!*2
1!=0!*1
Inny przykład:
5!=5*4!=5*4*3!=5*4*3*2!=5*4*3*2*1!=5*4*3*2*1*0!=5*4*3*2*1*1=120
Dana funkcja jest rekurencyjna jeśli zawiera odwołanie do samej siebie
2. Euklides z odejmowaniem (rekurencyjnie) – program
3. Liczby Fibonacciego – program
Aby policzyć liczby Fibonacciego można posłużyć się algorytmem iteracyjnym jak i rekurencyjnym. Jednak w tym przypadku algorytm w postaci rekurencyjnej wymaga wykonania dużo większej liczby kroków obliczeniowych niż ten sam algorytm w postaci iteracyjnej.
Funkcja Fibonacci jest wykonywana dwukrotnie wewnątrz siebie samej: raz z parametrem (n-1) a drugi raz z parametrem (n-2)
4. Schemat Hornera – program