在函数式语言程序更容易出现堆栈溢出？

Question

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

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

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

它必须最终导致堆栈溢出。如果我是应该做的事情相当于在C ++中（使用递归），我知道这会溢出。

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

Answer 1

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

所以，一个很快学会使用IS尾递归（和对当前总中累积作为参数），从而优化器可以做它的工作，即，可能O'Caml语法，其中I”的净的辅助功能米生锈：

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库堆栈安全版。大多数其他的实现做堆栈一个更好的工作。 （声明：我的信息描述目的CAML 3.08;当前版本，3.11，可能会更好）

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

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

Answer 5

这是棘手 - 原则上是的，但功能性的语言编译器和运行时占递归函数式语言增加的程度。最基本的是，大多数函数式语言运行时要求一个更大的堆栈比正常迭代程序将使用。但除了该函数式语言编译器更能够变换递归代码到非递归由于语言的更严格的限制。