Pasja IT - blog o informatyce

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...