Rekurencja w programowaniu...

Dzisiaj chciałbym omówić jedną z trudniejszych zagadnień programowania - mianowicie rekurencję. Rekurencja to zdolność podprogramu ( funkcji lub procedury ) do wywołania samej siebie. Najprostszym przykładem użycia rekurencji jest zaimplementowanie silni.

Silnię liczby naturalnej n oznaczamy symbolem n! i definiujemy jako iloczyn kolejnych liczb :

n!=1*2*3...*(n-1)*n 

Zauważmy, że funkcję obliczającą silnię możemy następująco zaimplementować :

• silnia(0)=1
• silnia(n)=n*silnia(n-1)

Możemy zauważyć, że w powyższym algorytmie została użyta rekurencja. Poniżej przedstawię funkcję wyliczającą silnię zakodowaną w języku Turbo Pacal.

function silnia(n : integer) : integer;

Begin

if (n=0) then silnia:=1;

else silnia:=n*silnia(n-1);

 End; 

Innym ciekawym przykładem zastosowania rekurencji jest algortym wyliczający największy wspólny dzielnik dla liczb naturalnych a i b.Oto skrócony algorytm :

if a*b=0 then NWD(a,b)=a+b

else if a>=b then NWD(a,b)=NWD(a mod b,b)

else NWD(a,b)=NWD(a, b mod a)

To wszystko. Pozdrawiam.