Scala是否支持尾递归优化？

Question

Scala是否支持尾递归优化？

Answer 1

正如其他海报所说,Scala在编译时进行尾递归优化.也就是说,尾递归函数由编译器转换为循环(方法调用转换为跳转),这可以从运行尾递归函数时的堆栈跟踪中看出.

请尝试以下代码段:

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

并检查堆栈跟踪.它只显示对函数繁荣的一次调用 - 因此编译的字节码不是递归的.

有一个提议在JVM级别实现尾调用 - 在我看来这是一件好事,因为JVM可以进行运行时优化,而不仅仅是编译代码的时间优化 - 并且可能意味着更多灵活的尾递归.基本上tailcall invoke会表现得完全像一个正常的方法invoke,但在安全情况下这样做将下降呼叫者的堆栈-即栈帧必须保留的JVM状态的规格,所以JIT必须做一些静态代码分析,找出如果永远不会使用堆栈帧.

目前的状态是原始的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支持对最终方法和本地函数的自递归(一个函数调用自身)进行尾调用优化.

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

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

Answer 4

只有在函数是自递归的非常简单的情况下.

尾递归能力的证明.

看起来Scala 2.8可能正在改进尾递归识别.