递归运行时实现Java与其他/函数语言?

tail recursion . 尾部递归意味着递归调用应该是递归方法的最后一个调用。然后,编译器可以将其优化为一个循环,防止发生堆栈溢出错误。

javac 实现实现尾部递归。这不是规范所要求的。然而,对于任何递归程序来说,它都是一种重要的优化技术,因此我认为主流实现确实提供了尾部递归。

StackOverflowError 并使其尾部递归(计算 factorial ,例如)。

question about tail recursion 如用户sje397的注释所示。还可以看看 Stephen C's answer 对于这个问题,它提供了一些额外的信息。

以下是@Ronald Wildenberg的回答:

我不确定是否所有javac实现都实现了尾部递归。这不是规范所要求的。

简而言之,他们不支持。

this blog entry 作者:johnrose@Oracle,他在那里谈到了这个问题。这篇博文的主旨是提出一个字节码扩展来支持“硬”尾部调用。但最后一段暗示了为什么实现“软”(即透明)尾部调用是困难的。尾部调用优化会干扰JVM捕获堆栈跟踪的能力,这对Java安全体系结构有“影响”。

这个 Sun Bug Database Entry 提供有关问题的更多详细信息。同时阅读评论。

“具有~100K次迭代的递归”是应该避免的,而不仅仅是在Java中。它只能通过尾部调用优化来工作,这并不总是可能的。所以最好不要养成过度递归的习惯。

您可以通过以下方法增加java堆栈大小:

java -Xss1024k MyProgram

支持深层(非尾部)递归的策略通常包含在支持一级连续性的策略中。你可能会发现 Implementation Strategies for First-Class Continuations (Clinger等人)有趣。

我脑子里有几个策略:

• 在堆栈溢出时,将堆栈复制到一个单独的内存块,并将堆栈指针重置到基;在下溢时,将旧堆栈复制回基
• 在堆栈溢出时,创建一个新线程以继续运行计算,并等待线程的结果(缺点:创建线程可能很昂贵(但工作线程可以被缓存),并且跨线程移动计算可能会导致线程本地存储等问题)