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

Question

I think there is @tailrec annotation 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)?

Answer 1

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

• In Scala 2.8, you will also be able to use the new @tailrec annotation 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.

Example:

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

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):

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 = {
                    ^

Answer 2

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

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.

Answer 3

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

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)

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

Here we import the annotation, and try to mark a method as @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:

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 length0 is automatically private because it is defined in the scope of another method.