Я пытаюсь реализовать хвостовую рекурсивную функцию сортировки списков в OCaml и получил следующий код:
let tailrec_merge_sort l =
let split l =
let rec _split source left right =
match source with
| [] -> (left, right)
| head :: tail -> _split tail right (head :: left)
in _split l [] []
in
let merge l1 l2 =
let rec _merge l1 l2 result =
match l1, l2 with
| [], [] -> result
| [], h :: t | h :: t, [] -> _merge [] t (h :: result)
| h1 :: t1, h2 :: t2 ->
if h1 < h2 then _merge t1 l2 (h1 :: result)
else _merge l1 t2 (h2 :: result)
in List.rev (_merge l1 l2 [])
in
let rec sort = function
| [] -> []
| [a] -> [a]
| list -> let left, right = split list in merge (sort left) (sort right)
in sort l
;;
Тем не менее, похоже, что на самом деле это не хвостовая рекурсия, поскольку я сталкиваюсь с ошибкой «Переполнение стека во время оценки (циклическая рекурсия?)».
Не могли бы вы помочь мне определить нерекурсивный вызов в этом коде? Я довольно много искал, но не нашел. Может, это привязка let в функции sort?
