performance - Does Scala support tail recursion optimization?

Question

Does Scala support tail recursion optimization?

Answer 1

正如其他海报所说，Scala 在编译时进行尾递归优化。也就是说，一个尾递归函数被编译器转换为一个循环（方法调用被转换为一个跳转），从运行尾递归函数时的堆栈跟踪可以看出。

尝试以下代码段：

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

并检查堆栈跟踪。它只会显示对函数 boom 的一次调用——因此编译后的字节码不是递归的。

有一个提议在 JVM 级别实现尾调用——在我看来这是一件好事，因为这样 JVM 可以进行运行时优化，而不仅仅是代码的编译时优化——并且可能意味着更多灵活的尾递归。基本上 a 的tailcall invoke行为与普通方法完全相同，invoke但在安全的情况下会丢弃调用者的堆栈 - JVM 的规范规定必须保留堆栈帧，因此 JIT 必须进行一些静态代码分析以找出如果堆栈帧永远不会被使用。

它的当前状态是proto 80%。我认为 Java 7 不会及时完成（invokedynamic具有更高的优先级，并且实现几乎完成），但 Java 8 可能会看到它实现。

Answer 2

在 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)
}

如果无法优化方法，则会出现编译时错误。

Answer 3

Scala 2.7.x 支持对 final 方法和本地函数的自递归（一个函数调用自身）进行尾调用优化。

Scala 2.8 也可能带有对 trampoline 的库支持，这是一种优化相互递归函数的技术。

可以在Rich Dougherty 的博客中找到有关 Scala 递归状态的大量信息。

Answer 4

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.