Why won't the Scala compiler apply tail call optimization unless a method is final?

Question

Why won't the Scala compiler apply tail call optimization unless a method is final?

For example, this:

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

results in

error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden

What exactly would go wrong if the compiler applied TCO in a case such as this?

Answer 1

Consider the following interaction with the REPL. First we define a class with a factorial method:

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 

Now let's override it in a subclass to double the superclass's answer:

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) 

What result do you expect for this last call? You might be expecting 240. But no:

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

That's because when the superclass's method makes a recursive call, the recursive call goes through the subclass.

If overriding worked such that 240 was the right answer, then it would be safe for tail-call optimization to be performed in the superclass here. But that isn't how Scala (or Java) works.

Unless a method is marked final, it might not be calling itself when it makes a recursive call.

And that's why @tailrec doesn't work unless a method is final (or private).

UPDATE: I recommend reading the other two answers (John's and Rex's) as well.