什么是 Scala 注释以确保优化尾递归函数？

What is the Scala annotation to ensure a tail recursive function is optimized?

提问by huynhjl

I think there is @tailrecannotation to ensure the compiler will optimize a tail recursive function. Do you just put it in front of the declaration? Does it also work if Scala is used in scripting mode (for instance using :load <file>under REPL)?

我认为有@tailrec注释可以确保编译器优化尾递归函数。你只是把它放在声明前面吗？如果在脚本模式下使用 Scala（例如:load <file>在 REPL下使用），它是否也有效？

回答by VonC

From the "Tail calls, @tailrec and trampolines" blog post:

来自“ Tail call、@tailrec 和trampolines”博客文章：

• In Scala 2.8, you will also be able to use the new @tailrecannotation to get information about which methods are optimised.
  This annotation lets you mark specific methods that you hope the compiler will optimise.
  You will then get a warning if they are not optimised by the compiler.
• In Scala 2.7 or earlier, you will need to rely on manual testing, or inspection of the bytecode, to work out whether a method has been optimised.

• 在 Scala 2.8 中，您还可以使用新的@tailrec注释来获取有关优化了哪些方法的信息。
  此注释可让您标记希望编译器优化的特定方法。
  如果编译器未优化它们，您将收到警告。
• 在 Scala 2.7 或更早版本中，您将需要依靠手动测试或字节码检查来确定方法是否已优化。

Example:

例子：

you could add a @tailrecannotation so that you can be sure that your changes have worked.

您可以添加@tailrec注释，以确保您的更改有效。

import scala.annotation.tailrec

class Factorial2 {
  def factorial(n: Int): Int = {
    @tailrec def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) acc
      else factorialAcc(n * acc, n - 1)
    }
    factorialAcc(1, n)
  }
}

---

---

And it works from the REPL (example from the Scala REPL tips and tricks):

它适用于 REPL（来自Scala REPL 提示和技巧的示例）：

C:\Prog\Scala\tests>scala
Welcome to Scala version 2.8.0.RC5 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_18).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.annotation.tailrec
import scala.annotation.tailrec

scala> class Tails {
     | @tailrec def boom(x: Int): Int = {
     | if (x == 0) throw new Exception("boom!")
     | else boom(x-1)+ 1
     | }
     | @tailrec def bang(x: Int): Int = {
     | if (x == 0) throw new Exception("bang!")
     | else bang(x-1)
     | }
     | }
<console>:9: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
       @tailrec def boom(x: Int): Int = {
                    ^
<console>:13: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
       @tailrec def bang(x: Int): Int = {
                    ^

回答by Dave Griffith

The Scala compiler will automatically optimize any truly tail-recursive method. If you annotate a method that you believe is tail-recursive with the @tailrecannotation, then the compiler will warn you if the method is actually not tail-recursive. This makes the @tailrecannotation a good idea, both to ensure that a method is currently optimizable and that it remains optimizable as it is modified.

Scala 编译器会自动优化任何真正的尾递归方法。如果您使用注释注释了一个您认为是尾递归的方法@tailrec，那么编译器会警告您该方法是否实际上不是尾递归的。这使得@tailrec注释成为一个好主意，既可以确保方法当前是可优化的，又可以在修改时保持可优化。

Note that Scala does not consider a method to be tail-recursive if it can be overridden. Thus the method must either be private, final, on an object (as opposed to a class or trait), or inside another method to be optimized.

请注意，Scala 不认为可以覆盖的方法是尾递归的。因此，该方法必须是私有的、最终的、对象上的（与类或特征相反），或者在另一个要优化的方法中。

回答by retronym

The annotation is scala.annotation.tailrec. It triggers a compiler error if the method can't be tail call optimized, which happens if:

注释是scala.annotation.tailrec。如果该方法无法进行尾调用优化，则会触发编译器错误，在以下情况下会发生：

1. The recursive call is not in the tail position
2. The method could be overriden
3. The method is not final (special case of the preceding)

1. 递归调用不在尾部位置
2. 该方法可以被覆盖
3. 该方法不是最终的（前面的特殊情况）

It is placed just before the defin a method definition. It works in the REPL.

它def位于方法定义中的 之前。它适用于 REPL。

Here we import the annotation, and try to mark a method as @tailrec.

这里我们导入注解，并尝试将方法标记为@tailrec.

scala> import annotation.tailrec
import annotation.tailrec

scala> @tailrec def length(as: List[_]): Int = as match {  
     |   case Nil => 0
     |   case head :: tail => 1 + length(tail)
     | }
<console>:7: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
       @tailrec def length(as: List[_]): Int = as match { 
                    ^

Oops! The last invocation is 1.+(), not length()! Let's reformulate the method:

哎呀！最后一次调用是1.+()，不是length()！让我们重新制定方法：

scala> def length(as: List[_]): Int = {                                
     |   @tailrec def length0(as: List[_], tally: Int = 0): Int = as match {
     |     case Nil          => tally                                       
     |     case head :: tail => length0(tail, tally + 1)                    
     |   }                                                                  
     |   length0(as)
     | }
length: (as: List[_])Int

Note that length0is automatically private because it is defined in the scope of another method.

请注意，它length0是自动私有的，因为它是在另一个方法的范围内定义的。