optimization - 在 JVM 中运行时在 Scala 中使用递归

Question

通过在本站点和 Web 上的其他地方搜索，JVM 不支持尾调用优化。因此，这是否意味着如果要在 JVM 上运行，则不应该编写尾递归 Scala 代码，例如以下可能在非常大的输入列表上运行的代码？

// Get the nth element in a list    
def nth[T](n : Int, list : List[T]) : T = list match {
            case Nil => throw new IllegalArgumentException
            case _ if n == 0 => throw new IllegalArgumentException
            case _ :: tail if n == 1 => list.head
            case _ :: tail  => nth(n - 1, tail)
}

Martin Odersky 的 Scala by Example 包含以下段落，这似乎表明存在适合递归的情况或其他环境:

In principle, tail calls can always re-use the stack frame of the calling function. However, some run-time environments (such as the Java VM) lack the primitives to make stack frame re-use for tail calls efficient. A production quality Scala implementation is therefore only required to re-use the stack frame of a di- rectly tail-recursive function whose last action is a call to itself. Other tail calls might be optimized also, but one should not rely on this across implementations.

谁能解释一下这一段中间两句是什么意思？

谢谢!

Answer 1

由于直接尾递归等效于 while 循环，因此您的示例将在 JVM 上高效运行，因为 Scala 编译器可以将其编译为引擎盖下的循环，只需使用跳转即可。然而，JVM 不支持一般 TCO，尽管有可用的 tailcall() 方法，该方法支持使用编译器生成的蹦床进行尾调用。

为了确保编译器可以正确地将尾递归函数优化为循环，您可以使用 scala.annotation.tailrec 注释，如果编译器无法进行所需的优化，则会导致编译器错误:

import scala.annotation.tailrec

@tailrec def nth[T](n : Int, list : List[T]) : Option[T] = list match {
            case Nil => None
            case _ if n == 0 => None
            case _ :: tail if n == 1 => list.headOption
            case _ :: tail  => nth(n - 1, tail)
}

(螺丝 IllegalArgmentException!)