Java中递归和非递归函数的效率比较

Question

Java中递归和非递归函数的效率比较

c#javarecursionperformance

6

据我所知，递归函数通常比等效的非递归函数效率低，因为函数调用的开销。然而，最近我遇到一本教材说，在Java（和C#）中并非总是如此。

它没有说明原因，但我认为这可能是因为Java编译器以某种方式优化了递归函数。

有人知道这是为什么吗？

- katsuya

http://www.amazon.com/Programming-Interviews-Exposed-Secrets-Programmer/dp/047012167X - katsuya

6个回答

4

这通常只适用于尾递归（http://en.wikipedia.org/wiki/Tail_call）。

尾递归在语义上等同于增量循环，因此可以优化为循环。以下是我链接文章中的一句话（重点在我这里）：

尾调用很重要，因为它们可以在不向调用堆栈添加新堆栈帧的情况下实现。当前过程的大部分框架不再需要，并且可以用相应的尾调用框架替换。然后程序可以跳转到被调用的子例程。生产这种代码而不是标准调用序列称为尾调用消除或尾调用优化。在函数式编程语言中，尾调用消除通常由语言标准保证，这个保证允许使用递归，特别是尾递归，代替循环。

- Travis Webb

我不了解Java/C#……他的书声称是这样，但我自己没有研究过。@Stephen则声称相反。 - Travis Webb

1

有趣的是，Scala是一种运行在JVM之上并生成字节码（可与Java字节码互换）的语言，采用函数式方法，鼓励使用递归函数，并生成尾递归调用的编译器。Scala社区希望在JVM本身中实现TCO，但目前还没有完成，也没有承诺。然而，永远不要忘记：过早地进行优化是万恶之源。 - user unknown

1

C#做到了。在CLR4中支持更好（并且在64位上运行最佳）。然而，某些情况下（例如尾调用到一个参数比调用者更多的方法），实际上作为尾调用比作为普通调用更慢。 - porges

1

.NET JIT实际上支持TCO。请参见http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx。 - SimonC

4

以下是递归实现在某些情况下可以与迭代实现一样有效的原因：

编译器可以聪明地优化掉某些函数的函数调用，例如将尾递归函数转换为循环。我强烈怀疑现代Java的JIT编译器中有些已经这样做了。
现代处理器进行分支预测和推测执行，这意味着函数调用的成本是最小的，或者至少不比迭代循环的成本高。
在需要每个递归级别上具有少量本地存储空间的情况下，通过递归函数调用将其放在堆栈上通常比以其他方式（例如通过堆内存中的队列）分配更有效。

然而，我的一般建议是不要担心这个问题-差异非常小，很不可能对您的整体性能产生影响。

- mikera

2

盖伊·斯蒂尔是Java之父之一，他在1977年写了一篇论文。

    Debunking the "Expensive Procedure Call" Myth
or, Procedure Call Implementations Considered Harmful
          or, LAMBDA: The Ultimate GOTO

摘要：民间说法认为GOTO语句是“廉价的”，而过程调用则是“昂贵的”。这种说法在很大程度上是由于设计不良的语言实现所造成的。

有趣的是，即使在今天，Java仍然没有尾递归优化。

- irreputable

1

据我所知，Java不会进行任何递归优化。了解这一点很重要——不是因为效率，而是因为过度深度的递归（几千次应该就足够了）会导致堆栈溢出并使程序崩溃。（考虑到这个网站的名字，我很惊讶之前没有人提到过这一点）。

- Mike Baranczak

0

我认为不是这样的，在像UVA或SPOJ这样的网站解决一些编程问题的经验中，我必须删除递归才能在规定的时间内解决问题。

你可以考虑的一种方法是：在递归调用中，每次递归发生时，jvm必须为被调用的函数分配资源，在非递归函数中，大部分内存已经分配好了。

- JeanK

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stephen C · Accepted Answer

这本教材可能在提到尾递归优化；有关详细信息，请参见@Travis的答案。然而，在Java环境下，这本教材是错误的。目前的Java编译器没有实现尾递归优化，显然是因为它会干扰Java安全实现，并且会改变那些检查调用栈以达到不同目的应用程序的行为。参考文献：1.JVM是否禁止尾调用优化？ 2.这个Sun bug请求尾调用支持……仍然开放。3.这个页面（以及引用的论文）表明，也许这并不难...。有迹象表明，尾调用优化可能会进入Java 8。