Scala 是否支持尾递归优化？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1677419/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Does Scala support tail recursion optimization?
提问by Roman Kagan
Does Scala support tail recursion optimization?
Scala 是否支持尾递归优化？
回答by Flaviu Cipcigan
Scala does tail recursion optimisation at compile-time, as other posters have said. That is, a tail recursive function is transformed into a loop by the compiler (a method invoke is transformed into a jump), as can be seen from the stack trace when running a tail recursive function.
正如其他海报所说，Scala 在编译时进行尾递归优化。即尾递归函数被编译器转化为循环（方法调用转化为跳转），从运行尾递归函数时的堆栈轨迹可以看出。
Try the following snippet:
尝试以下代码段：
def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)
and inspect the stack trace. It will show only one call to the function boom - therefore the compiled bytecode is not recursive.
并检查堆栈跟踪。它将只显示对函数 bom 的一次调用 - 因此编译的字节码不是递归的。
There is a proposal floating around to implement tail calls at the JVM level- which in my opinion would a great thing to do, as then the JVM could do runtime optimizations, rather than just compile time optimizations of the code - and could possibly mean more flexible tail recursion. Basically a tailcall invokewould behave exactly like a normal method invokebut will drop the stack of the caller when it's safe to do so - the specification of the JVM states that stack frames must be preserved, so the JIT has to do some static code analysis to find out if the stack frames are never going to be used.
有一个提议在 JVM 级别实现尾调用- 在我看来这是一件很棒的事情，因为 JVM 可以进行运行时优化，而不仅仅是代码的编译时优化 - 并且可能意味着更多灵活的尾递归。基本上 a 的tailcall invoke行为与普通方法完全一样，invoke但会在安全的情况下丢弃调用者的堆栈 - JVM 的规范规定必须保留堆栈帧，因此 JIT 必须进行一些静态代码分析才能找出如果永远不会使用堆栈帧。
The current status of it is proto 80%. I don't think it will be done in time for Java 7 (invokedynamichas a greater priority, and the implementation is almost done) but Java 8 might see it implemented.
它的当前状态是proto 80%。我不认为它会在 Java 7 中及时完成（invokedynamic具有更高的优先级，并且实现几乎完成）但 Java 8 可能会看到它实现。
回答by Vitalii Fedorenko
In Scala 2.8 you can use @tailrecto mark specific method that you expect the compiler will optimise:
在 Scala 2.8 中，您可以使用@tailrec来标记您希望编译器优化的特定方法：
import scala.annotation.tailrec
@tailrec def factorialAcc(acc: Int, n: Int): Int = {
if (n <= 1) acc
else factorialAcc(n * acc, n - 1)
}
If a method can not be optimized you get a compile-time error.
如果无法优化方法，则会出现编译时错误。
回答by Daniel C. Sobral
Scala 2.7.x supports tail-call optimization for self-recursion (a function calling itself) of final methods and local functions.
Scala 2.7.x 支持最终方法和局部函数的自递归（调用自身的函数）的尾调用优化。
Scala 2.8 might come with library support for trampoline too, which is a technique to optimize mutually recursive functions.
Scala 2.8 也可能带有对trampoline 的库支持，这是一种优化相互递归函数的技术。
A good deal of information about the state of Scala recursion can be found in Rich Dougherty's blog.
关于 Scala 递归状态的大量信息可以在Rich Dougherty 的博客中找到。
回答by Stefan Kendall
Only in very simple cases where the function is self-recursive.
仅在函数是自递归的非常简单的情况下。
Proof of tail recursion ability.
It looks like Scala 2.8 might be improving tail-recursion recognition, though.
不过，看起来 Scala 2.8 可能会改进尾递归识别。
