Rekurencja ogonowa

Rekursja ogonowa (albo rekurencja ogonowa) to rekursja po której nie następuje już powrót do funkcji. Jest bardzo ważnym pojęciem, gdyż stosując taką rekursję można w ogóle nie używać stosu - jest ona równie wydajna jak imperatywna pętla.

Bardzo często funkcja taka ma dwa argumenty - właściwy argument oraz dotychczasowy wynik, i jako warunek bazowy ma zwrócenie dotychczasowego wyniku jako wyniku ostatecznego. Np. (ocaml):

let rec suma wynik = function
    []   -> wynik
  | a::b -> suma (a+wynik) b

Obliczenia które zachodzą dla suma 0 [1;2;3;4] to:

suma 0 [1;2;3;4] - wywołanie funkcji

suma 0 1::[2;3;4] - dopasowanie do wzorca

suma (1+0) [2;3;4] - obliczenie wyrażenia

suma 1 [2;3;4] - rekursja ogonowa

suma 1 2::[3;4] - dopasowanie do wzorca

suma (2+1) [3;4] - obliczenie wyrażenia

suma 3 [3;4] - rekursja ogonowa

suma 3 3::[4] - dopasowanie do wzorca

suma (3+3) [4] - obliczenie wyrażenia

suma 6 [4] - rekursja ogonowa

suma 6 4::[] - dopasowanie do wzorca

suma (4+6) [] - obliczenie wyrażenia

suma 10 [] - przypadek bazowy

10 - koniec obliczeń