11

从本网站和网络上的其他地方搜索，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 包含以下段落，这似乎表明存在适合递归的情况或其他环境：

原则上，尾调用总是可以重用调用函数的栈帧。但是，一些运行时环境（例如 Java VM）缺乏使堆栈帧重用于尾调用高效的原语。因此，生产质量的 Scala 实现只需要重用直接尾递归函数的堆栈帧，该函数的最后一个操作是调用自身。其他尾调用也可能会被优化，但不应依赖于跨实现。

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

谢谢！

4

5 回答 5

22

由于直接尾递归等效于 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！）

于 2011-04-17T20:56:48.640 回答
19

原则上，尾调用总是可以重用调用函数的栈帧。但是，一些运行时环境（例如 Java VM）缺乏使堆栈帧重用于尾调用高效的原语。因此，生产质量的 Scala 实现只需要重用直接尾递归函数的堆栈帧，该函数的最后一个操作是调用自身。其他尾调用也可能会被优化，但不应依赖于跨实现。

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

尾递归是尾调用的一种特殊情况。直接尾递归是尾递归的一种特殊情况。只有直接尾递归才能保证被优化。其他的也可能被优化，但这基本上只是一个编译器优化。作为一种语言特性，Scala 只保证直接消除尾递归。

那么，有什么区别呢？

好吧，尾调用只是子例程中的最后一个调用：

def a = {
  b
  c
}

在这种情况下，调用c是尾调用，调用b不是。

尾递归是当尾调用调用之前已经调用过的子例程时：

def a = {
  b
}

def b = {
  a
}

这是尾递归：a调用b（尾调用），而后者又a再次调用。（与下面描述的直接尾递归相反，这有时称为间接尾递归。）

但是，这两个示例都不会被 Scala 优化。或者，更准确地说：Scala 实现可以优化它们，但不是必须这样做。这与例如 Scheme 形成对比，其中语言规范保证所有上述情况都将占用O(1)堆栈空间。

Scala 语言规范仅保证直接尾递归得到优化，即当子例程直接调用自身而中间没有其他调用时：

def a = {
  b
  a
}

在这种情况下，调用a是尾调用（因为它是子程序中的最后一次调用），它是尾递归（因为它再次调用自己），最重要的是它是直接尾递归，因为a直接调用自己而不经过先打另一个电话。

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

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

  1. 您不能对尾递归方法执行提取方法重构，至少不包括尾调用，因为这会将直接尾递归方法（将得到优化）转变为间接尾递归方法（不会得到优化）。
  2. 您只能使用直接尾递归。可以使用间接尾递归非常优雅地表达的尾递归下降解析器或状态机已经过时了。

主要原因是当你的底层执行引擎缺乏强大的控制流操作特性，例如GOTO，延续，一流的可变堆栈或适当的尾调用，那么你需要在它上面实现你自己的堆栈，使用蹦床，进行全局 CPS 变换或类似的讨厌的东西，以提供通用的正确尾调用。所有这些都会对性能或与同一平台上的其他代码的互操作性产生严重影响。

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

长话短说：是的，您发布的具体示例将被优化，因为它是直接尾递归。您可以通过@tailrec在方法上添加注释来测试它。注释不会改变方法是否被优化，但是它保证如果方法不能被优化，你会得到一个编译错误。

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

于 2011-04-18T02:23:59.463 回答
3

Scala 编译器将尝试通过将尾调用“展平”为不会导致堆栈不断扩展的循环来优化尾调用。

当然，您的代码必须是可优化的。但是，如果您在方法之前使用注释 @tailrec (scala.annotation.tailrec)，编译器将要求该方法可优化或无法编译。

于 2011-04-17T20:57:44.783 回答
2

请注意，有些JVM支持尾调用优化（IIRC，IBM 的 J9 支持），这不是 JLS 中的要求，Oracle 的实现也没有这样做。

于 2011-04-18T09:55:33.853 回答
2

Martin 的评论是，只有直接自递归调用才是 TCO 优化的候选对象（满足其他标准）。间接的、相互递归的方法对（或更大的递归方法集）不能如此优化。

于 2011-04-17T22:07:33.327 回答