46

为什么除非方法是最终的，否则 Scala 编译器不会应用尾调用优化？

例如，这个：

class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}

结果是

错误：无法优化 @tailrec 注释方法：它既不是私有的也不是最终的，因此可以被覆盖

如果编译器在这种情况下应用TCO ，究竟会出现什么问题？

4

5 回答 5

56

考虑以下与 REPL 的交互。首先我们用阶乘方法定义一个类：

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

现在让我们在子类中覆盖它以使超类的答案加倍：

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

您对最后一次通话的预期结果是什么？您可能期待 240。但没有：

scala> (new C2).fact(5, 1)
res13: Int = 7680

那是因为当超类的方法进行递归调用时，递归调用会经过子类。

如果覆盖工作使得 240 是正确答案，那么在此处的超类中执行尾调用优化将是安全的。但这不是 Scala（或 Java）的工作方式。

除非一个方法被标记为 final，否则它在进行递归调用时可能不会调用自己。

这就是为什么@tailrec 不起作用的原因，除非方法是最终的（或私有的）。

更新：我建议也阅读其他两个答案（约翰和雷克斯）。

于 2011-01-24T18:25:20.637 回答
23

递归调用可能是对子类而不是对超类；final将防止这种情况。但是为什么你会想要这种行为呢？斐波那契数列没有提供任何线索。但这确实：

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

如果 Pretty 调用是尾递归的，我们会打印出来，{Set(0, 1),1}因为扩展不适用。

由于这种递归似乎很有用，并且如果允许对非最终方法的尾调用会被破坏，因此编译器会插入一个真正的调用。

于 2011-01-24T18:39:11.417 回答
7

让foo::fact(n, res)表示你的例程。让baz::fact(n, res)表示其他人对您的例程的覆盖。

编译器告诉你语义允许baz::fact()成为一个包装器，如果它愿意，它可以调用 (?) 。foo::fact()在这种情况下，规则是foo::fact()，当它递归时，必须激活baz::fact()而不是激活foo::fact()，并且，虽然foo::fact()是尾递归，baz::fact()但可能不是。到那时，不是在尾递归调用上循环，而是foo::fact()必须返回到baz::fact()，以便它可以自行展开。

于 2011-01-24T18:26:06.967 回答
1

如果编译器在这种情况下应用 TCO，究竟会出现什么问题？

什么都不会出错。任何具有适当尾调用消除的语言都可以做到这一点（SML、OCaml、F#、Haskell 等）。Scala 不支持的唯一原因是 JVM 不支持尾递归，并且 Scala 通常将尾位置的自递归调用替换为的技巧goto在这种情况下不起作用。CLR 上的 Scala 可以像 F# 一样做到这一点。

于 2013-08-12T21:05:16.300 回答
0

这个问题的流行和接受的答案实际上具有误导性，因为这个问题本身就是令人困惑的。OP没有区分tailrecand TCO，答案也没有解决这个问题。

关键是对的要求tailrec比对的要求更严格TCO。

该tailrec注释要求对同一函数进行尾调用，而TCO可以在对任何函数的尾调用中使用。

编译器可以使用TCOonfact因为在尾部位置有一个调用。具体来说，它可以通过适当调整堆栈将调用转换fact为跳转。fact这个版本与fact进行调用的函数不同并不重要。

所以接受的答案正确地解释了为什么非最终函数不能是tailrec因为你不能保证尾调用是对同一个函数而不是对函数的重载版本。但它错误地暗示TCO在这种方法上使用是不安全的，而事实上这将是完全安全的并且是一个很好的优化。

[请注意，正如 Jon Harrop 所解释的，您不能TCO在 JVM 上实现，但这是编译器的限制，而不是语言的限制，并且与tailrec]

作为参考，以下是如何在不使用该方法的情况下避免该问题final：

class C {
  def fact(n: Int): Int = {
    @tailrec
    def loop(n: Int, result: Int): Int =
      if (n == 0) {
        result
      } else {
        loop(n - 1, n * result)
      }

    loop(n, 1)
  }
}

这是有效的，因为loop它是一个具体的函数而不是一个方法，并且不能被覆盖。此版本还具有去除虚假result参数的优点fact。

这是我用于所有递归算法的模式。

于 2019-02-27T12:35:07.277 回答