OCaml
Rekurencja ogona
Szukaj…
Wprowadzenie
Języki funkcjonalne, takie jak OCaml, w dużej mierze polegają na funkcjach rekurencyjnych . Jednak takie funkcje mogą powodować nadmierne zużycie pamięci lub, w przypadku obsługi dużych zestawów danych, przepełnienie stosu .
W takich przypadkach rekurencja ogona jest ważnym źródłem optymalizacji. Pozwala programowi na usunięcie kontekstu dzwoniącego, gdy wywołanie rekurencyjne jest ostatnim z funkcji .
Funkcja sumy
Poniżej znajduje się niekursywna funkcja rekurencyjna do obliczania sumy listy liczb całkowitych.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
Ostatnią operacją, którą wykonuje funkcja, jest dodanie. Zatem funkcja nie jest rekurencyjna.
Poniżej znajduje się wersja rekurencyjna tej samej funkcji.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Tutaj funkcja aux jest rekurencyjna: ostatnia wykonywana operacja wywołuje się sama. W rezultacie ta ostatnia wersja sum może być używana z listami o dowolnej długości.