functional-programming - 函数式语言的程序是否更容易出现堆栈溢出？

Question

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

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

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

它最终必须导致堆栈溢出。如果我在 C++ 中做同样的事情(使用递归)，我知道它会溢出。

所以我的问题是，是否有内置的保护措施来防止函数式语言溢出堆栈？如果不是，它们是不是不太有用，因为上面的求和算法是用 for 循环的程序风格编写的，可以处理任何数字(不考虑整数溢出)？

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

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