5

我开始学习 ocaml，并且非常欣赏这种语言中递归的力量。但是，我担心的一件事是堆栈溢出。

如果ocaml使用堆栈进行函数调用，最终不会溢出堆栈吗？例如，如果我有以下功能：

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

它最终必须导致堆栈溢出。如果我要在 c++ 中做同样的事情（使用递归），我知道它会溢出。

所以我的问题是，是否有内置的保护措施来防止函数式语言溢出堆栈？如果不是，它们是不是像这样不那么有用，因为上面的求和算法，以带有 for 循环的程序风格编写，可以处理任何数字（不考虑整数溢出）？

4

5 回答 5

11

所有（;-) 函数式语言的体面实现都优化了尾递归，但这不是你在这里做的，因为递归调用不是最后的操作（它需要跟在加法之后）。

因此，人们很快就会学会使用一个尾递归的辅助函数（并将当前累积的总数作为参数），这样优化器就可以完成它的工作，即排除我生锈的可能的 O'Caml 语法：

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

在这里，总和作为递归调用的参数发生，即在递归本身之前，因此可以启动尾部优化（因为递归是需要发生的最后一件事！）。

于 2009-08-18T02:02:49.467 回答
6

函数式语言通常具有更大的堆栈。例如，我已经编写了一个专门用于测试 OCaml 中的堆栈限制的函数，并且在它被吐出之前它得到了超过 10,000 次调用。但是，您的观点是有效的。堆栈溢出仍然是函数式语言中需要注意的事情。

函数式语言用来减轻对递归的依赖的策略之一是使用尾调用优化。如果对当前函数的下一个递归的调用是函数中的最后一条语句，则可以从堆栈中丢弃当前调用，并在其位置实例化新调用。生成的汇编指令与命令式的while循环基本相同。

您的函数不是尾调用可优化的，因为递归不是最后一步。它需要先返回，然后才能将 x 添加到结果中。通常这很容易解决，您只需创建一个辅助函数，将累加器与其他参数一起传递

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;
于 2009-08-18T02:04:03.757 回答
4

一些函数式语言如 Scheme 规定尾递归 必须优化为等效于迭代；因此，Scheme 中的尾递归函数永远不会导致堆栈溢出，无论它递归多少次（当然，假设它在结尾之外的其他地方也不会递归或参与相互递归）。

大多数其他函数式语言不需要高效实现尾递归。有些选择这样做，有些则没有，但它相对容易实现，所以我希望大多数实现都这样做。

于 2009-08-18T01:59:20.237 回答
4

新手很容易写出破坏堆栈的深度递归。Objective Caml 的不寻常之处在于，对于长列表，库List函数不是堆栈安全的。像Unison这样的应用程序实际上已经List用堆栈安全版本替换了 Caml 标准库。大多数其他实现在堆栈方面做得更好。（免责声明：我的信息描述了 Objective Caml 3.08；当前版本 3.11 可能更好。）

新泽西州的标准 ML不寻常，因为它不使用堆栈，因此您的深度递归会继续进行，直到您用完堆为止。它在 Andrew Appel 的优秀著作Compiling with Continuations中有描述。

我不认为这里有严重的问题。这更像是一个“意识点”，如果你要编写大量递归代码，你更有可能用函数式语言来做，你必须注意非尾调用和堆栈大小与您将要处理的数据的大小相比。

于 2009-08-18T02:18:46.077 回答
1

这很棘手——原则上是的，但是函数式语言的编译器和运行时解释了函数式语言中递归程度的增加。最基本的是，大多数函数式语言运行时请求的堆栈比普通迭代程序使用的堆栈要大得多。但除此之外，由于语言的更严格的约束，函数式语言编译器更能够将递归代码转换为非递归代码。

于 2009-08-18T02:05:46.220 回答