Rekursja ogonowa
Z Wikipedii
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ń
