Хвостовая рекурсия

Из Википедии

Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.

https://ru.wikipedia.org/wiki/Хвостовая_рекурсия

Оптимизация

Использование хвостовой рекурсии позволяет компилятору оптимизировать её в эффективную итерацию. Если вам важна эффективность, то старайтесь укладывать ваш алгоритм в рамках хвостовой рекурсии.

Типичный пример хвостовой и не хвостовой рекурсии

Рекурсия.

let rec sum = function
| [] -> 0
| hd::tl -> hd + sum tl

Хвостовая рекурсия.

let sum =
  let rec aux acc = function
    | [] -> acc
    | hd::tl -> aux (hd + acc) tl
  in aux 0

Внутренние вспомогательные функции

Для реализации хвостовой рекурсии нужна внутрення аккумулятивная переменная. Поэтому обычно внутри функции пишут рекурсивную вспомогательную-функцию.

Пример

Helper-функция loop.

let reverse list =
  let loop rev_list list = (* реализация *)
  in loop [] list

Это является хорошей практикой.

Частые названия helper-функций

• loop
• aux от слова auxiliary
• go если вы знакомы с Haskell 😃

Аннотации

Про аннотации смотрите в мануале.

tailcall

Аннотация tailcall может быть применена к применению функции, чтобы проверить, что вызов оптимизирован для хвостовой рекурсии. Если это не так, выдается предупреждение.

(* Хвостовая рекурсия. *)
let rec is_a_tail_call = function
  | [] -> ()
  | _ :: q -> (is_a_tail_call[@tailcall]) q

(* Не хвостовая. *)
let rec not_a_tail_call = function
  | [] -> []
  | x :: q -> x :: (not_a_tail_call[@tailcall]) q
(* Warning 51 [wrong-tailcall-expectation]:  *)

tail_mod_cons

Документация

The “Tail Modulo Constructor” program transformation