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.