我喜欢递归，但在 Java 中你有时会遇到死胡同。例如，我遇到过约 100K 次迭代的递归不起作用的情况（StackOverflowError）。不幸的是，由于运行时堆栈限制的原因，我不得不切换到烦人的“命令循环”。
我想知道其他（尤其是函数式）语言如何在运行时绕过堆栈溢出？我想特别是函数式语言运行时可以更好地处理这个问题，因为递归是核心概念......
有人有一些信息或外部资源吗？
I like recursion, but at Java you meet an dead end at some point. E.g. I had a case where recursion with ~100K iterations wouldn't work (StackOverflowError). Badly I had to switch to annoying "imperative looping" for this runtime stack-limit reasons.
I wonder how other (especially functional) languages bypass stack-overflowing during runtime? I guess especially functional language runtimes handle this problem better because recursion is core-concept...
Has somebody some information or external resources?
发布评论
评论（5）
大多数语言都针对尾递归进行了编译器优化。尾递归意味着递归调用应该是递归方法的最后一次调用。然后，编译器可以将其优化为循环，从而防止发生堆栈溢出错误。
我不确定是否所有 javac 实现都实现尾递归。这不是规范所要求的。然而，对于任何递归程序来说，它都是一种重要的优化技术，因此我认为主流实现确实提供了尾递归。
您可以通过使用一个（简单的）非尾递归程序来自行测试这一点，该程序会生成 StackOverflowError 并使其成为尾递归（计算 阶乘，例如）。
编辑：有一个关于尾递归的问题< /a> 之前在 Java 中，如用户 sje397 的评论中所示。另请查看 Stephen C 的回答对于这个问题，它提供了一些额外的信息。
Most languages have compiler optimizations for tail recursion. Tail recursion means that the recursive call should be the last call of your recursive method. The compiler can then optimize this into a loop, preventing stack overflow errors from happening.
I'm not sure whether all
javacimplementations implement tail recursion. It is not something that is required by the specification. However, it's an important optimization technique for any recursive program, so I suppose the mainstream implementations do provide tail recursion.You can test this yourself by taking a (simple) non-tail-recursive program that generates a
StackOverflowErrorand make it tail-recursive (calculating a factorial, for example).EDIT: There has been a question about tail recursion in Java before, as indicated in a comment by user sje397. Also take a look at Stephen C's answer to this question, which provides some additional info.
这是@Ronald Wildenberg 答案的后续内容：
简短的回答是他们不支持。
更长的答案是，由于 JVM 的设计，尾递归优化在 Java 中是一个棘手的问题。阅读 John Rose @ Oracle 的这篇博客文章，他在其中讨论了这个问题。该博客条目的主旨是提出字节码扩展以支持“硬”尾调用。但最后一段暗示了为什么实现“软”（即透明）尾部调用很困难。尾部调用优化会干扰 JVM 捕获堆栈跟踪的能力，这对 Java 安全架构有“影响”。
此 Sun Bug 数据库条目提供了有关该问题的更多详细信息。也请阅读评论。
看来现在的JVM上实现尾递归的方式就是在编译器前端实现。显然 Scala 就是这样做的。
This is a followup to @Ronald Wildenberg's answer:
The short answer is that they don't support it.
The longer answer is that tail recursion optimization is a tricky problem in Java because of the JVM design. Read this blog entry by John Rose @ Oracle where he talks about this problem. The main thrust of the blog entry is a proposal for a bytecode extension to support "hard" tail calls. But the last paragraph hints as why implementing "soft" (i.e. transparent) tail calls is hard. Tail call optimization interferes with the JVM's ability to capture a stack trace, and that has "implications" for the Java security architecture.
This Sun Bug Database Entry gives more details on the problem. Read the comments as well.
It seems that the way to implement tail recursion on the current JVM is to implement it in the compiler front-end. Apparently Scala does this.
“递归约 100K 次迭代”是应该避免的事情，不仅仅是在 Java 中。它仅由于尾部调用优化而起作用，但这并不总是可行的。因此，最好一开始就不要养成过度递归的习惯。
递归是人们在第一次学习时往往会过度使用的概念之一，因为不到处炫耀似乎太酷了……
"recursion with ~100K iterations" is something that should be avoided, not just in Java. It works only due to tail call optimization, which is not always possible. So it's better not to get into the habit of excessive recursion in the first place.
Recursion is one of those concepts people tend to overuse when they first learn them, because it seems just too cool not to show off everywhere...
您可以通过以下方式增加 java 堆栈大小：（
会将 java 堆栈大小增加到 1024 KB。）
但一般来说，使用深度递归并不是一个好主意。尝试制定迭代解决方案。
You can increase java stack size with:
(will increase the stack size of java upto 1024 KB.)
But generally it is not a good idea to use that deep recursion. Try to make iterative solution.
正如其他人提到的，支持适当的尾递归会有所帮助。但它本身不足以支持深度递归。不管 BLUB 程序员可能怎么想，深度递归非常适合某些任务，例如处理深度递归数据结构。
支持深度（非尾）递归的策略通常包含在支持一流延续的策略中。您可能会发现一流延续的实施策略（ Clinger 等人）很有趣。
我想到了一些策略：
As other people have mentioned, support for proper tail recursion helps. But by itself it's not enough to support deep recursion. And despite what BLUB programmers might think, deep recursion is a natural fit for some tasks, such as processing deeply recursive data structures.
Strategies for supporting deep (non-tail) recursion are often subsumed by strategies for supporting first-class continuations. You might find Implementation Strategies for First-Class Continuations (Clinger et al) interesting.
A few strategies off the top of my head: