如何制作尾递归函数并测试它？

Question

我想使这个函数递归，但我不知道从哪里开始。

let rec rlist r n =
    if n < 1 then []
    else Random.int r :: rlist r (n-1);;

let rec divide = function
    h1::h2::t -> let t1,t2 = divide t in
        h1::t1, h2::t2
    | l -> l,[];;

let rec merge ord (l1,l2) = match l1,l2 with
    [],l | l,[] -> l
    | h1::t1,h2::t2 -> if ord h1 h2
        then h1::merge ord (t1,l2)
        else h2::merge ord (l1,t2);;

有什么方法可以测试函数是否递归？

Answer 1

您可以执行以下操作：

let rlist r n =
  let aux acc n =
    if n < 1 then acc
    else aux (Random.int r :: acc) (n-1)
  in aux [] n;;

let divide l =
  let aux acc1 acc2 = function
    | h1::h2::t -> 
        aux (h1::acc1) (h2::acc2) t
    | [e] -> e::acc1, acc2
    | [] -> acc1, acc2
  in aux [] [] l;;

但是对于除法，我更喜欢这个解决方案：

 let divide l =
   let aux acc1 acc2 = function
     | [] -> acc1, acc2
     | hd::tl -> aux acc2 (hd :: acc1) tl
   in aux [] [] l;;

let merge ord (l1,l2) = 
  let rec aux acc l1 l2 = 
    match l1,l2 with
      | [],l | l,[] -> List.rev_append acc l
      | h1::t1,h2::t2 -> if ord h1 h2
        then aux (h1 :: acc) t1 l2
        else aux (h2 :: acc) l1 t2
  in aux [] l1 l2;;

关于你关于测试一个函数是否是尾递归的问题，通过仔细寻找它你会找到它 here。

Answer 2

If you give a man a fish, you feed him for a day. But if you give him a fishing rod, you feed him for a lifetime.

所以与其给你解决方法不如教你自己解决

尾递归函数是一种递归函数，所有的递归调用都在尾部位置。如果调用位置是函数中的最后一次调用，即被调用函数的结果将成为调用者的结果，则调用位置称为尾部位置。

让我们以下面的简单函数作为我们的工作示例：

let rec sum n = if n = 0 then 0 else n + sum (n-1)

它不是尾递归函数，因为调用 sum (n-1) 不在尾部位置，因为它的结果然后递增 1。将一般递归函数转换为尾递归形式并不总是那么容易。有时，需要在效率、可读性和尾递归之间进行权衡。

一般的技巧是：

使用累加器
使用连续传递样式

使用累加器

有时一个函数确实需要存储中间结果，因为递归的结果必须以一种非平凡的方式组合。递归函数为我们提供了一个自由容器来存储任意数据——调用堆栈。语言运行时存储当前调用函数的参数的地方。不幸的是，堆栈容器是有界的，它的大小是不可预测的。所以，有时候，最好从栈切换到堆。后者稍微慢一些（因为它给垃圾收集器引入了更多的工作），但更大且更可控。在我们的例子中，我们只需要一个词来存储运行和，所以我们有明显的胜利。我们正在使用更少的 space，并且我们没有引入任何内存垃圾：

let sum n = 
  let rec loop n acc = if n = 0 then acc else loop (n-1) (acc+n) in
  loop n 0

但是，如您所见，这需要权衡取舍 - 实施变得更大且更难理解。

我们在这里使用了一个通用模式。由于我们需要引入一个累加器，因此我们需要一个额外的参数。由于我们不想或不能更改我们函数的接口，我们引入了一个新的辅助函数，它是递归的并且将携带额外的参数。这里的技巧是我们在执行递归调用之前应用求和，而不是之后。

使用连续传递样式

并非总是可以使用累加器重写递归算法。在这种情况下，可以使用更通用的技术——连续传递样式。基本上，它与之前的技术很接近，但我们将使用延续来代替累加器。延续是一个函数，它实际上会将递归之后需要完成的工作推迟到以后的时间。按照惯例，我们称此函数为 return 或简称为 k（为了延续）。在心理上，延续是一种将计算结果抛回未来的方式。 “返回”是因为您 return 将结果返回给调用者，在将来，因为，结果不会现在使用，而是在一切准备就绪后使用。但是让我们看看实现：

let sum n = 
  let rec loop n k = if n = 0 then k 0 else loop (n-1) (fun x -> k (x+n)) in
  loop n (fun x -> x)

你可能会看到，我们采用了相同的策略，除了我们使用函数 k 作为第二个参数而不是 int 累加器。如果基本情况，如果 n 为零，我们将 return 0，（您可以将 k 0 读为 return 0）。在一般情况下，我们在尾部位置递归，归纳变量 n 有规律地递减，但是，我们将工作打包，应该用递归函数的结果完成到一个函数中：fun x -> k (x+n)。基本上，这个函数表示，一旦 x - 递归调用的结果准备就绪，将其添加到数字 n 和 return 中。（同样，如果我们使用名称 return 而不是 k，它可能更具可读性：fun x -> return (x+n)）。

这里没有魔法，我们仍然有与累加器相同的权衡，因为我们在每次递归调用时创建一个新的闭包（功能对象）。每个新创建的闭包都包含对前一个闭包的引用（通过参数传递）。例如，fun x -> k (x+n) 是一个函数，它捕获两个自由变量，值 n 和函数 k，这是之前的延续。基本上，这些延续形成一个链表，其中每个节点都承担一个计算和除一个之外的所有参数。因此，计算会延迟到知道最后一个。

当然，对于我们这个简单的例子来说，没有必要使用CPS，因为它会产生不必要的垃圾，而且速度会慢很多。这仅用于演示。但是，对于更复杂的算法，特别是那些在非平凡情况下组合两个或多个递归调用结果的算法，例如折叠图数据结构。

所以现在，有了新的知识，我希望你能够轻松解决你的问题。

尾递归测试

尾调用是一个非常明确的句法概念，所以调用是否在尾位置应该是很明显的。但是，仍然很少有方法可以检查调用是否处于尾部位置。事实上，还有其他情况，尾调用优化可能会发挥作用。例如，对短路逻辑运算符的正确调用也是尾调用。因此，当调用使用堆栈或它是尾调用时，并不总是很明显。新版本的 OCaml 允许在调用处添加注释，例如

let rec sum n = if n = 0 then 0 else n + (sum [@tailcall]) (n-1)

如果调用不是真正的尾调用，编译器会发出警告：

Warning 51: expected tailcall

另一种方法是使用-annot选项编译。注释文件会包含每次调用的注释，例如，如果我们将上述函数放入文件sum.ml并使用ocamlc -annot sum.ml编译，那么我们可以打开sum.annot文件并查看所有电话：

"sum.ml" 1 0 41 "sum.ml" 1 0 64
call(
  stack
)

但是，如果我们放置第三个实现，那么会发现所有调用都是尾调用，例如grep call -A1 sum.annot:

call(
  tail
--
call(
  tail
--
call(
  tail
--
call(
  tail

最后，你可以用一些大的输入来测试你的程序，看看你的程序是否会因堆栈溢出而失败。您甚至可以减少堆栈的大小，这可以通过环境变量 OCAMLRUNPARAM 来控制，例如，将堆栈限制为一千个单词：

export OCAMLRUNPARAM='l=1000'
ocaml sum.ml

如何制作尾递归函数并测试它？

How to make an tail recursive function and test it?

recursion

ocaml

tail-recursion

使用累加器

使用连续传递样式

尾递归测试