Klasyczny program rekurencyjny będzie wyglądał następująco:
let rec silnia n = if n = 0 then 1 else n * silnia (n - 1)
Nie korzysta on z rekurencji ogonowej, przez co obliczenie od strony interpretera będzie wyglądać następująco:
Wywołaj silnia(3) Wywołaj silnia(2) Wywołaj silnia(1) Wywołaj silnia(0) Zwróć 1 Zwróć 1 Zwróć 2 Zwróć 6
Możemy wprowadzić tutaj rekurencję ogonową, zauważając że w przypadku mnożenia kolejność wykonywania obliczeń nie gra żadnej roli. Stworzymy zatem funkcję pomocniczą, z dodatkowym argumentem (akumulatorem), w którym do kolejnych wywołań będzie przekazywany aktualny wynik. Gdy licznik dojdzie do zera, funkcja zwróci wartość akumulatora jako wynik końcowy:
let rec sil n acc = if n = 0 then acc else sil (n-1) (n*acc)
let rec silnia n = sil n 1
Działanie programu będzie wyglądać następująco:
Wywołaj silnia(3) Wywołaj sil(3,1) Zastąp argumenty (3,1) przez (2,3), skocz na początek sil Zastąp argumenty (2,3) przez (1,6), skocz na początek sil Zastąp argumenty (1,6) przez (0,6), skocz na początek sil Zwróć 6 jako wynik Zwróć 6
Zobacz też derekursywacja
Przypisy
Bibliografia
Kategoria:Rekurencja