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.

  1. 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
  2. efekt odbicia w lustrze nakierowanego na inne lustro
  3. 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

  1. Rekurencyjna definicja silni liczby naturalnej n -> program

schemat blokowy silni (rekurencyjnie)
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 Fibonacciegoprogram
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)

http://images.slideplayer.pl/12/3774037/slides/slide_9.jpg
4. Schemat Hornera – program