Java中递归与非递归函数的效率比较
据我了解，由于函数调用的开销，递归函数通常比等效的非递归函数效率低。然而，我最近遇到一本教科书，说对于 Java（和 C#）来说这不一定是真的。
它没有说明原因，但我认为这可能是因为 Java 编译器以某种方式优化了递归函数。
有谁知道为什么会这样的细节？
As I understand, recursive functions are generally less efficient than equivalent non-recursive functions because of the overhead of function calls. However, I have recently encountered a text book saying this is not necessary true with Java (and C#).
It does not say why, but I assume this might be because the Java compiler optimizes recursive functions in some way.
Does anyone know the details of why this is so?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
教科书可能指的是尾部调用优化；有关详细信息，请参阅@Travis 的答案。
然而，教科书在 Java 的上下文中是不正确的。当前的 Java 编译器没有实现尾部调用优化，显然是因为它会干扰 Java 安全实现，并且会改变出于各种目的在调用堆栈上进行内省的应用程序的行为。
参考文献：
有迹象表明尾部调用优化可能会进入 Java 8。
The text book is probably referring to tail-call optimization; see @Travis's answer for details.
However, the textbook is incorrect in the context of Java. Current Java compilers do not implement tail-call optimization, apparently because it would interfere with the Java security implementation, and would alter the behaviour of applications that introspect on the call stack for various purposes.
References:
There are hints that tail-call optimization might make it into Java 8.
这通常仅适用于尾递归（http://en.wikipedia.org/wiki/Tail_call）。
尾递归在语义上等同于增量循环，因此可以优化为循环。以下是我链接到的文章的引用（强调我的）：
This is usually only true for tail-recursion (http://en.wikipedia.org/wiki/Tail_call).
Tail-recursion is semantically equivalent to an incremented loop, and can therefore be optimized to a loop. Below is a quote from the article that I linked to (emphasis mine):
在某些情况下，递归实现可以与迭代实现一样高效的一些原因：
不过，我的一般建议是不必担心这一点 - 差异非常小，不太可能对您的整体表现产生影响。
Some reasons why recursive implementations can be as efficient as iterative ones under certain circumstances:
My general advice however is don't bother worrying about this - the difference is so small that it is very unlikely to make a difference in your overall performance.
Java 之父之一 Guy Steele 在 1977 年写了一篇论文
这很有趣，因为即使在今天，Java 也没有尾部调用优化:)
Guy Steele, one of the fathers of Java, wrote a paper in 1977
That's funny, because even today, Java has no tail call optimization:)
据我所知，Java不进行任何形式的递归优化。知道这一点很重要 - 不是因为效率，而是因为过度深度的递归（几千次就可以了）会导致堆栈溢出并导致程序崩溃。 （真的，考虑到这个网站的名称，我很惊讶没有人在我面前提到这个）。
To the best of my knowledge, Java does not do any sort of recursion optimization. Knowing this is important - not because of efficiency, but because recursion at an excessive depth (a few thousand should do it) will cause a stack overflow and crash your program. (Really, considering the name of this site, I'm surprised nobody brought this up before me).
根据我在 UVA 或 UVA 或 < a href="http://www.spoj.pl/" rel="nofollow">SPOJ 我必须删除递归才能在规定的时间内解决问题。
你可以想到的一种方式是：在递归调用中，每当递归发生时，jvm都必须为被调用的函数分配资源，在非递归函数中，大部分内存已经分配。
I don't think so, in my experience in solving some programming problems in sites like UVA or SPOJ I had to remove the recursion in order to solve the problem within established time to solve the problem.
One way that you can think is: in recursive calls, any time that the recursion occurs, the jvm must allocate resources for the function that has being called, in non recursive functions most part of the memory is already allocated.