函数式语言的程序更容易出现堆栈溢出吗？
我开始学习 ocaml，并且非常欣赏该语言中递归的力量。然而，我担心的一件事是堆栈溢出。
如果ocaml使用堆栈进行函数调用，最终不会导致堆栈溢出吗？例如，如果我有以下函数：
let rec sum x =
if x > 1 then f(x - 1) + x
else x;;
它最终一定会导致堆栈溢出。如果我在 C++ 中做同样的事情（使用递归），我知道它会溢出。
所以我的问题是，是否有内置的保护措施来防止函数式语言溢出堆栈？如果不是，那么它们是不是不太有用，因为上面的求和算法是用 for 循环以程序风格编写的，可以处理任何数字（不考虑整数溢出）？
I am starting to learn ocaml, and am really appreciating the power of recursion in the language. However, one thing that I am worried about is stack overflows.
If ocaml uses the stack for function calls, won't it eventually overflow the stack? For example, if I have the following function:
let rec sum x =
if x > 1 then f(x - 1) + x
else x;;
it must eventually cause a stack-overflow. If I was to do the equivalent thing in c++ (using recursion), I know that it would overflow.
So my question is, is there built in safeguards to prevent functional languages from overflowing the stack? If not, are they not less useful like this, since the above summing algorithm, written in a procedural style with a for loop, could handle any number (dis-regarding integer overflow)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
所有（适当的实现；-）函数语言都会优化尾递归，但这不是您在这里所做的，因为递归调用不是最后一个操作（它需要后面跟着加法）。
因此，人们很快就会学会使用尾递归的辅助函数（并将当前累积的总数作为参数），以便优化器可以完成其工作，即排除我生疏的可能的 O'Caml 语法：
在这里，总和作为递归调用的参数发生，即在递归本身之前，因此尾部优化可以启动（因为递归是最后需要发生的事情！）。
All (decent implementations of;-) functional languages optimize tail recursion, but that's not what you're doing here, since the recursive call is not the LAST operation (it needs to be followed by the addition).
So, one soon learns to use an auxiliary function that IS tail recursive (and takes the current total being accumulated as an argument) so the optimizer can do its job, i.e., net of possible O'Caml syntax in which I'm rusty:
Here, the sum happens as an ARGUMENT to the recursive call, i.e., BEFORE the recursion itself, and so tail optimization can kick in (because the recursion IS the last thing that needs to happen!).
函数式语言通常具有更大的堆栈。例如，我专门编写了一个函数来测试 OCaml 中的堆栈限制，它在崩溃之前调用了超过 10,000 次。不过，你的观点是有道理的。在函数式语言中，堆栈溢出仍然是您需要注意的事情。
函数式语言用来减轻对递归的依赖的策略之一是使用尾调用优化。如果对当前函数的下一个递归的调用是函数中的最后一个语句，则可以从堆栈中丢弃当前调用，并在其位置实例化新调用。生成的汇编指令与命令式风格的 while 循环的汇编指令基本相同。
您的函数不可进行尾部调用优化，因为递归不是最后一步。它需要先返回，然后才能将 x 添加到结果中。通常这很容易解决，您只需创建一个辅助函数来传递累加器以及其他参数
Functional languages typically have a MUCH larger stack. For example, I've written a function specifically to test stack limits in OCaml, and it got to over 10,000 calls before it barfed. However, your point is valid. Stack-overflows are still something you need to watch out for in functional languages.
One of the strategies that functional languages use to mitigate their reliance on recursion is the use of tail-call optimization. If the call to the next recursion of the current function is the last statement in the function, the current call can be discarded from the stack and the new call instantiated in its place. The assembly instructions that are generated will be basically the same as the ones for while-loops in imperative style.
Your function is not tail-call optimizable because the recursion is not the last step. It needs to return first and then it can add x to the result. Usually this is easy to get around, you just create a helper function that passes an accumulator along with the other parameters
一些函数式语言（例如Scheme）指定尾递归必须进行优化相当于迭代；因此，Scheme 中的尾递归函数永远不会导致堆栈溢出，无论它递归多少次（当然，假设它除了末尾之外的其他地方也不会递归或参与相互递归）。
大多数其他函数式语言不需要尾递归来有效实现；有些选择这样做，有些则不这样做，但它相对容易实现，所以我希望大多数实现都会这样做。
Some functional languages such as Scheme specify that tail recursion must be optimized to be equivalent to iteration; hence, a tail-recursive function in Scheme will never result in a stack overflow, no matter how many times it recurses (presuming, of course, that it doesn't also recurse or engage in mutual recursion in other places besides the end).
Most other functional languages don't require tail recursion to be implemented efficiently; some choose to do so, others do not, but it's relatively easy to implement, so I would expect that most implementations do so.
对于新手来说，编写导致堆栈崩溃的深度递归当然很容易。 Objective Caml 的不同寻常之处在于库
List函数对于长列表来说不是堆栈安全的。像 Unison 这样的应用程序实际上已经取代了 Caml 标准List具有堆栈安全版本的库。大多数其他实现在堆栈方面做得更好。 （免责声明：我的信息描述的是 Objective Caml 3.08；当前版本 3.11 可能更好。）新泽西州标准 ML< /a> 的不同寻常之处在于它不使用堆栈，因此深度递归会继续进行，直到用完堆为止。 Andrew Appel 的优秀著作 Compiling with Continuations 对此进行了描述。
我不认为这里有什么严重的问题；这更多的是一个“意识点”，如果您要编写大量递归代码（您更有可能使用函数式语言来完成此操作），您必须了解非尾调用和堆栈大小，如下所示与您要处理的数据大小相比。
It's certainly easy for novices to write deep recursions that blow the stack. Objective Caml is unusual in that the library
Listfunctions are not stack-safe for long lists. Applications like Unison have actually replaced the Caml standardListlibrary with a stack-safe version. Most other implementations do a better job with the stack. (Disclaimer: my information describes Objective Caml 3.08; the current version, 3.11, may be better.)Standard ML of New Jersey is unusual in that it doesn't use a stack, so your deep recursions keep going until you run out of heap. It's described in Andrew Appel's excellent book Compiling with Continuations.
I don't think there's a serious problem here; it's more a "point of awareness" that if you are going to be writing a lot of recursive code, which you're more likely to do in a functional language, you have to be aware of non-tail calls and of stack size as compared to the size of the data you'll be processing.
这很棘手——原则上是的，但是函数式语言的编译器和运行时解释了函数式语言中递归程度的增加。
最基本的是，大多数函数式语言运行时都需要比正常迭代程序使用的堆栈大得多的堆栈。
但除此之外，由于语言的约束更加严格，函数式语言编译器更能够将递归代码转换为非递归代码。
This is tricky -- in principle yes, but the compilers and runtimes for functional languages account for the increased degree of recursion in functional languages.
The most basic is that most functional language runtimes request a much larger stack than normal iterative programs would use.
But in addition to that, a functional language compiler is much more able to transform recursive code into a non-recursive due to the much stricter constraints of the language.