OCaml
Рекурсия хвоста
Поиск…
Вступление
Функциональные языки, такие как OCaml, сильно зависят от рекурсивных функций . Однако такие функции могут привести к перераспределению памяти или при обработке больших наборов данных для переполнения стека .
Регрессия хвоста является важным источником оптимизации в таких случаях. Это позволяет программе отбрасывать контекст вызывающего абонента, когда рекурсивный вызов является последним из функции .
Функция суммы
Ниже приведена не-хвостовая рекурсивная функция для вычисления суммы списка целых чисел.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
Последней операцией, которую выполняет функция, является добавление. Таким образом, функция не является хвостовой рекурсивной.
Ниже приведена хвостовая рекурсивная версия той же функции.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Здесь функция aux является хвостовой рекурсивной: последняя выполняемая им операция вызывает сам вызов. Как следствие, последняя версия sum может использоваться со списками любой длины.