java - 递归运行时实现 Java 与其他/功能语言？

Question

我喜欢递归，但在 Java 中，您有时会遇到死胡同。例如。我有一个案例，其中 ~100K 迭代的递归不起作用(StackOverflowError)。糟糕的是，由于这个运行时堆栈限制的原因，我不得不切换到烦人的“命令式循环”。

我想知道其他(尤其是函数式)语言如何在运行时绕过堆栈溢出？我想特别是函数式语言运行时可以更好地处理这个问题，因为递归是核心概念......

有人有一些信息或外部资源吗？

Answer 1

大多数语言都针对 tail recursion 进行了编译器优化.尾递归意味着递归调用应该是递归方法的最后一次调用。然后编译器可以将其优化为一个循环，防止发生堆栈溢出错误。

我不确定是否所有的 javac 实现都实现了尾递归。这不是规范所要求的。然而，它是任何递归程序的重要优化技术，所以我认为主流实现确实提供了尾递归。

您可以通过(简单的)非尾递归程序自行测试，该程序生成 StackOverflowError 并使其成为尾递归(例如，计算 factorial)。

编辑:有一个question about tail recursion以前在 Java 中，如用户 sje397 的评论中所示。另请查看 Stephen C's answer这个问题提供了一些额外的信息。