Why overrideable tail recursive methods must not be optimized

Suppose you define a tail recursive method x in a object A. You can use the @tailrec annotation to mark methods you expect optimization of the tail recursive code to happen.

import annotation._
object A{
    @tailrec def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

Now you move the method x to a trait or class and suddenly the compilation fails.

import annotation._
trait A{
    @tailrec def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

:8: error: could not optimize @tailrec annotated method
            @tailrec def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s

I had exactly this problem. I defined a perfectly valid tail recursive function but the compiler would not optimize it to a loop. This was in Scala 2.7 that does not support the @tailrec annotation. You have the additional issue of spotting the problem in the first place.

The problem is that overrideable tail recursive methods won't be optimized. If you change the code to

import annotation._
trait A{
    @tailrec final def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

it will compile again. This is the rule. But why?

Performance optimization must not change the behavior at run-time. So overriding an optimized tail recursive method will behave differently from an unoptimized tail recursive method.

Let's define A in a way that it won't be optimized and override the tail recursive method x in the subclass B.

class A{
    def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

class B extends A{
    override def x(i : Int, s: String) : String = super.x(i, s + "b:")
}

This will produce the output:

scala> new A().x(3, "")
res0: String = a:3a:2a:1

scala> new B().x(3, "")
res1: String = b:a:3b:a:2b:a:1b:

The implementation of the method x in B invokes the method x in A. When the method x defined in A invokes the method x it calls the method x in B (for an instance of B). This behavior is due to late binding of calls to x.

Suppose it was possible to optimize the method x in A. The compiler would define a class similar to this definition of A. The recursive invocation of x is optimized to a loop. With this definition of x there is no possibility to apply late binding to x. The optimization would hard wire the definition of x.

class A{
    def x(i : Int, s : String) : String = {
        var j = i
        var t = s
        while(j > 0){
            t = t + "a:" + j
            j = j - 1
        }
        t
    }
}

class B extends A{
    override def x(i : Int, s: String) : String = super.x(i, "b:" + s)
}

scala> new A().x(3, "")
res0: String = a:3a:2a:1

scala> new B().x(3, "")
res1: String = b:a:3a:2a:1

The early binding of x in A changes the behavior of B. Once the method x in A is called it will never come back to B. This is the reason why the Scala compiler can't optimize overrideable tail recursive methods.

Following this explanation, it should be clear that the @tailrec annotation is worthwhile and should be used in all your Scala 2.8 code you expect the optimization to happen. For Scala 2.7 it's a bit unfortunate that moving a tail recursive method from an object to trait will change the behavior significantly without a compiler error. So be warned.