在JVM中运行时，Scala中递归的使用

Question

从这个网站和网络上搜索得知，JVM不支持尾调用优化。那么这是否意味着像下面这样的尾递归Scala代码不应该在JVM上运行，尤其是在处理大型输入列表时？

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

马丁·奥德斯基的《Scala by Example》中包含以下段落，似乎表明在某些情况或其他环境下递归是合适的：

“原则上，尾调用总是可以重复使用调用函数的堆栈帧。然而，一些运行时环境（例如Java虚拟机）缺乏使尾调用的堆栈帧重用变得高效的基本操作。因此，生产质量的Scala实现仅需要重用直接尾递归函数的堆栈帧，其最后一个动作是对自身的调用。其他尾调用也可能被优化，但不能指望跨实现进行这种优化。”

请问有人能解释一下这段话的中间两句话是什么意思吗？

谢谢！

- gw111zz

---

可能是 https://dev59.com/fXVD5IYBdhLWcg3wDXF3 的重复问题。 - Jean-Philippe Pellet

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!）

- Kris Nuttycombe

Answer 2

尾调用原则是指可以重复使用调用函数的栈框架。然而，有些运行环境（如Java虚拟机）缺乏使尾调用的栈帧重用变得有效的原语。因此，生产质量的Scala实现只需要重用最后一个动作为对自身的调用的直接递归函数的栈帧。其他尾调用也可能被优化，但不能在实现之间依赖此功能。 Tail recursion是尾调用的一种特殊情况。 直接尾递归是尾递归的一种特殊情况。只有直接尾递归得到保证会被优化。其他的尾调用也可能会被优化，但这基本上只是编译器的优化。作为一种语言特性，Scala仅保证直接尾递归消除。 尾调用是子程序中的最后一个调用。

def a = {
  b
  c
}

在这种情况下，对于c的调用是尾调用，对于b的调用则不是。

尾递归是指尾调用调用了之前已经调用过的子程序：

def a = {
  b
}

def b = {
  a
}

这是尾递归：a 调用 b（一个尾调用），接着又调用了 a。（与下面描述的直接尾递归相对应，这有时被称为间接 尾递归。）

然而，Scala 不会优化这两个示例中的任何一个。或者更准确地说：Scala 实现允许对它们进行优化，但不要求如此。这与 Scheme 不同，在 Scheme 中，语言规范保证所有以上情况将占用O(1)栈空间。

Scala 语言规范仅保证对直接尾递归进行优化，即当子程序直接调用自身且中间没有其他调用时：

def a = {
  b
  a
}

在这种情况下，对a的调用是尾调用（因为它是子例程中的最后一个调用），它是尾递归（因为它再次调用自己），最重要的是它是直接尾递归，因为a直接调用自己，而不是首先通过另一个调用进行。

请注意，有许多微妙的事情可能导致方法不是直接尾递归。例如，如果a被重载，则递归实际上可能会通过不同的重载进行，因此将不再是直接递归。

在实践中，这意味着两件事情：

1.您无法对尾递归方法执行Extract Method Refactoring，至少不包括尾调用，因为这将把一个直接尾递归方法（它将得到优化）变成一个间接尾递归方法（它将不会得到优化）。 2.您只能使用直接尾递归。尾递归下降解析器或状态机，这可以使用间接尾递归非常优雅地表示，都不行。

这主要是因为当底层执行引擎缺乏强大的控制流操纵功能，如GOTO、continuations、first-class mutable stack或proper tail calls时，您需要在其上实现自己的堆栈、使用trampolines、进行全局CPS转换或类似麻烦的东西，以提供广义适当的尾呼叫。所有这些都对性能或与同一平台上其他代码的互操作性有严重影响。

或者，正如Clojure的创建者Rich Hickey在面临相同问题时所说：“性能、Java互操作性、尾调用。选择两个。”Clojure和Scala都选择在尾递归方面做出妥协，并且仅提供尾递归而不是完整的尾调用。

长话短说：是的，您发布的特定示例将得到优化，因为它是直接尾递归。您可以通过在方法上放置@tailrec注释来测试此功能。注释不会更改方法是否得到优化，但它确实保证如果无法优化该方法，则会收到编译错误。

由于上述微妙之处，通常最好在需要优化的方法上放置@tailrec注释，既为了获得编译错误，也为了向维护您的代码的其他开发人员提供提示。

- Jörg W Mittag

Answer 3

Scala编译器会尝试通过将“尾调用”转换为不会引起不断扩展堆栈的循环来优化其性能。

当然，您的代码必须可以进行优化才能实现。但是，如果您在方法前使用注释@tailrec（scala.annotation.tailrec），编译器将要求该方法可优化，否则将无法编译。

- Brendan W. McAdams

Answer 4

马丁的话意味着只有符合其他条件的直接自身递归调用才是尾递归优化的候选项。间接的、相互递归的方法对或者更大的递归方法集合无法进行此种优化。

- Randall Schulz

Answer 5

请注意，有一些JVM支持尾调用优化（如果我没记错，IBM的J9就支持），但这并不是JLS的要求，Oracle的实现不支持。

- Landei