[Solved]-Why won't the Scala compiler apply tail call optimization unless a method is final?-scala

The popular and accepted answer to this question is actually misleading, because the question itself is confusing. The OP does not make the distinction between tailrec and TCO, and the answer does not address this.

The key point is that the requirements for tailrec are more strict than the requirements for TCO.

The tailrec annotation requires that tail calls are made to the same function, whereas TCO can be used on tail calls to any function.

The compiler could use TCO on fact because there is a call in the tail position. Specifically, it could turn the call to fact into a jump to fact by adjusting the stack appropriately. It does not matter that this version of fact is not the same as the function making the call.

So the accepted answer correctly explains why a non-final function cannot be tailrec because you cannot guarantee that the tail calls are to the same function and not to an overloaded version of the function. But it incorrectly implies that it is not safe to use TCO on this method, when in fact this would be perfectly safe and a good optimisation.

[ Note that, as explained by Jon Harrop, you cannot implement TCO on the JVM, but that is a restriction of the compiler, not the language, and is unrelated to tailrec ]

And for reference, here is how you can avoid the problem without making the method final:

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

    loop(n, 1)
  }
}

This works because loop is a concrete function rather than a method and cannot be overridden. This version also has the advantage of removing the spurious result parameter to fact.

This is the pattern I use for all recursive algorithms.

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

Nothing would go wrong. Any language with proper tail call elimination will do this (SML, OCaml, F#, Haskell etc.). The only reason Scala does not is that the JVM does not support tail recursion and Scala's usual hack of replacing self-recursive calls in tail position with goto does not work in this case. Scala on the CLR could do this as F# does.

Let foo::fact(n, res) denote your routine. Let baz::fact(n, res) denote someone else's override of your routine.

The compiler is telling you that the semantics allow baz::fact() to be a wrapper, that MAY upcall (?) foo::fact() if it wants to. Under such a scenario, the rule is that foo::fact(), when it recurs, must activate baz::fact() rather than foo::fact(), and, while foo::fact() is tail-recursive, baz::fact() may not be. At that point, rather than looping on the tail-recursive call, foo::fact() must return to baz::fact(), so it can unwind itself.

Recursive calls might be to a subclass instead of to a superclass; final will prevent that. But why might you want that behavior? The Fibonacci series doesn't provide any clues. But this does:

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

If the Pretty call was tail-recursive, we'd print out {Set(0, 1),1} instead since the extension wouldn't apply.

Since this sort of recursion is plausibly useful, and would be destroyed if tail calls on non-final methods were allowed, the compiler inserts a real call instead.