如何制作尾递归函数并对其进行测试？

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 rec sum n = if n = 0 then 0 else n + sum (n-1)

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

一般的技术是：

1. 使用蓄能器
2. 使用延续传递风格

使用蓄能器

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

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（用于延续）。从心理上讲，延续是一种将计算结果扔回未来的方式。“返回”是因为你将结果返回给调用者，在未来，因为结果不会现在被使用，而是一旦一切准备就绪。但是让我们看看实现：

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)

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

这里没有魔法，我们仍然有与累加器相同的权衡，因为我们在每次递归调用时创建一个新的闭包（功能对象）。每个新创建的闭包都包含对前一个闭包的引用（通过参数传递）。例如，fun x -> k (x+n)是一个函数，它捕获两个自由变量 valuen和 function 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