OCaml 中的尾递归

Question

我正在尝试使用尾递归在 OCaml 中实现合并功能，但我遇到了尴尬的结果。谁能帮我解决这个问题。提前致谢。

let rec merge_helper l1 l2 accum = 
match l1 with
[] -> l2@accum
| hd::tl -> (match l2 with
    [] -> l1@accum
    |x::xs -> merge_helper tl xs l1@l2@accum);;
let merge l1 l2 = merge_helper l1 l2 [];;

merge [1;2;4] [3;4;5];;
- : int list = [4; 5; 2; 4; 4; 5; 1; 2; 4; 3; 4; 5]

Answer 1

首先，您的实现不会运行在常量堆栈 space 中。 xs @ ys 操作不是尾递归的，并且会进行 List.length xs 调用（因此使用这个数量的堆栈帧）。此外，merge 函数通常会保留顺序。所以你需要有一个比较函数，它将比较列表的元素。尚不清楚您对 merge 函数的期望，以及为什么将结果归类为怪异。对我来说，结果与代码匹配。对我来说很奇怪的是，虽然你正在解构 l1 和 l2 你没有使用解构的结果并添加整个列表 l1 和 l2到累加器。

方法应该是这样的，从第一个列表中取出一个元素，将这个元素添加到累加器中，然后切换列表。所以算法的归纳步骤如下：

 let rec loop acc xs ys = match xs with
   ...
   | x::xs -> loop (x::acc) ys xs

但是如果你想合并两个排序列表保持顺序，那么你需要在每一步都取两个列表中的最小元素。

let merge cmp xs ys = 
    let rec loop xs ys zs = match xs,ys with
      | [],ss|ss,[] -> List.rev_append zs ss
      | x :: txs, y :: tys -> 
         if cmp x y <= 0 
         then loop txs ys (x::zs)
         else loop xs tys (y::zs) in
    loop xs ys []

这里在归纳步骤中，我们取较小的元素，并继续两个列表：较小元素的所有者的尾部（因为它被移入累加器），第二个列表完全取（因为它没有积累任何东西）。由于我们在前面添加元素，它们将以相反的顺序排列，因此我们需要一些东西来反转结果（尾递归的通常权衡）。基本情况允许我们缩短我们的算法，当一个或另一个列表较短时，我们不再需要一个接一个地比较它们，并且可以将较长列表的其余部分附加到累加器 zs。我们使用 List.rev_append 将列表的剩余尾部附加到我们的累加器。此函数会将第一个列表的反向版本添加到第二个列表中。

OCaml 中的尾递归

Tail recursion in OCaml

recursion

ocaml

tail-recursion