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;Beginif (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.
