在函数式语言程序更容易出现堆栈溢出？(Are programs in functional lang

我开始学习ocaml的，和我真正欣赏递归的力量的语言。但是，有一点，我担心的是堆栈溢出。

如果ocaml的使用堆栈的函数调用，会不会它最终使栈溢出？举例来说，如果我有以下功能：

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

它必须最终导致堆栈溢出。如果我是做在C等价的东西++（使用递归），我知道这会溢出。

所以我的问题是，是否有内置的保障措施，以防止功能性语言溢出堆栈？如果没有，他们不喜欢这个用处不大，因为上述加法的算法，编写一个程序风格的for循环，可以处理任何数量（DIS-有关整数溢出）？

Answer 1:

所有（;-)函数式语言的得体实现优化尾递归，但是这不是你在这里做什么，因为递归调用不是最后一个操作（它需要被随后加入）。

所以，一个很快学会使用是尾递归（并对当前总被累积作为参数），以便优化器可以完成自己的工作，也就是，其中我是生锈的可能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);;

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

Answer 2:

功能性语言通常有一个更大的堆栈。例如，我写了一个函数专门测试OCaml中堆栈限制，它有它barfed之前超过10000个呼叫。但是，你的观点是正确的。栈溢出依然是你需要注意函数式语言的东西。

一个函数式语言使用，以减轻其对递归依赖的策略是利用尾调用优化。如果调用当前函数的递归旁边是函数的最后一条语句，当前呼叫可以从堆栈并在其位置实例化的新的呼叫被丢弃。所生成的汇编指令将基本相同，那些在命令行式风格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;;

Answer 3:

一些功能性的语言，如方案指定尾递归必须优化为等同于迭代; 因此，在方案一尾递归函数永远不会导致堆栈溢出，无论有多少次递归（假设，当然，它不也递归或从事除结束等地相互递归）。

大多数其他函数式语言不需要尾递归能够高效地实现; 有些人选择这样做，其他人不这样做，但它是比较容易实现的，所以我希望多数实现这样做。

Answer 4:

这当然是很容易的新手编写吹堆栈深递归。目的CAML的特别之处库List功能不能叠加，安全的长列表 。像应用齐奏实际上已经取代了CAML标准List与堆栈安全版本库。大多数其他的实现做堆栈一个更好的工作。（免责声明：我的信息描述语言Objective Caml 3.08;当前版本3.11，可能会更好。）

新泽西州的标准ML是，它不使用堆栈异常，所以你深深的递归继续下去，直到你用完了堆。它在安德鲁阿佩尔的优秀图书描述与延续编译。

我不认为这里有一个严重的问题; 那就是，如果你将要编写大量的递归代码，你就更有可能在功能性语言做，你必须要知道的非尾调用和堆栈大小为多了一个“意识点”相比你会被处理的数据的大小。