Charakterystyczną cechą funkcji (procedury) rekurencyjnej jest to, że wywołuje ona samą siebie. Drugą cechą rekursji jest jej dziedzina, którą mogą być tylko liczby naturalne.
Najłatwiej zrozumieć mechanizm działania rekursji na przykładzie silni: rekurencyjny wzór na obliczenie n! zapisuje się w ten sposób: n!=n*(n-1)!
Ze wzoru tego wynika, że aby obliczyć np. 4!, należy najpierw obliczyć 3!. Ale żeby obliczyć 3! trzeba obliczyć 2! itd. aż dojdziemy do 0!, które jak wiemy wynosi 1.
Sposób obliczenia 4! wygląda więc następująco:
4!=4*3!=4*3*2!=4*3*2*1!=4*3*2*1*0!=4*3*2*1*1=24
Przykładowa implementacja funkcji rekurencyjnej obliczającej n! wygląda tak:

function silnia(n:integer):integer;
begin
if (n=0)or(n=1) then silnia:=1 else
silnia:=n*silnia(n-1);
end;

Inny przykład zastosowania rekursji to Ciąg Fibonacciego.
Pojawia się pytanie, czy warto stosować rekursję? Odpowiedz nie jest jednoznaczna. Funkcje rekurencyjne mają dużą złożoność obliczeniową a ponad to wymagają zastosowania wewnętrznego stosu. Należy więc ich unikać. Niestety zlikwidowanie rekursji jest czasami bardzo trudne i wymaga sporych umiejętności. Są jednak przypadki, w których likwidacja rekursji jest możliwa i prosta, na przykład omawiana przez nas silnia daje się przedstawić w postaci iteracji (zob. Silnia).

Komentarze