函数式语言中的程序更容易发生堆栈溢出？ [英] Are programs in functional languages more likely to have stack overflows?

问题描述

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

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

  let rec sum x = 
 if x> 1然后f（x  -  1）+ x 
 else x ;; 
  

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

所以我的问题是，是否内置防止功能溢出堆栈的语言？如果不是这样，那么它们是不是像这样有用，因为上面用for循环写成的程序风格的求和算法可以处理任何数字（无关的整数溢出）？

因此，很快学会使用一个尾递归的辅助函数（并且将当前的总和作为参数进行累加），所以优化器可以完成它的工作，即，我可能会生锈的O'Caml语法的网络：

  let sum x = 
 aux（x ）（0）;; 
 
 let rec aux x accum = 
 if x> 1则aux（x-1）（accum + x）
 else（accum + x）;; 
  

在这里，总和作为递归调用的一个自变量，也就是说，在递归本身之前，所以尾巴优化可以踢进去（因为递归是最后一件事情！）。

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)?

解决方案

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:

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

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

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!).

这篇关于函数式语言中的程序更容易发生堆栈溢出？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！