函数式语言中的程序是否更有可能出现堆栈溢出？

Question

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

如果ocaml使用堆栈进行函数调用,它最终是否会溢出堆栈？例如,如果我有以下功能:

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

它必须最终导致堆栈溢出.如果我在c ++(使用递归)中做相同的事情,我知道它会溢出.

所以我的问题是,是否有内置的安全措施来防止函数式语言溢出堆栈？如果不是这样,它们是不是没那么有用,因为上面的求和算法,用带有for循环的过程样式编写,可以处理任何数字(不相关的整数溢出)？

Answer 1

所有(()函数语言的优秀实现都优化了尾递归,但这不是你在这里所做的,因为递归调用不是LAST操作(需要后跟添加).

因此,很快就会学会使用一个IS尾递归的辅助函数(并将当前总数作为参数累积),这样优化器就可以完成它的工作,即可能的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);;

这里,总和作为递归调用的ARGUMENT发生,即在递归本身之前,因此尾部优化可以启动(因为递归是最后需要发生的事情!).

Answer 2

功能语言通常具有更大的堆栈.例如,我已经编写了一个专门用于测试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;;