Tail call optimization in general works by reusing current stack frame, instead of creating another one. Reusing current stack frame means nothing else than destroying entire local state of fuction (including instruction pointer) and then setting up new function parameters (instruction pointer is set to beginning of function). In order for that to be sound the only allowed actions after a tail call are either nothing or returning a value immediately.
In your example above after recursive call you can have more work to do in current method invocation - that’s why reusing stack frame can’t be done there.
To be clear, a function can have multiple tail calls and still be eligible for full tail call optimization. The only requirement is the one I’ve stated above - after tail call the only allowed work is returning the value immediately.
Because tail call optimization requires returning values immediately functions need some transformation before applying the optimization. E.g: this list reversal is not eligible for tail call optimization:
def reverse[A](list: List[A]): List[A] = {
list match {
case x :: xs => reverse(xs) ::: List(x)
case Nil => Nil
}
}
After recursive call reverse(xs)
we need to concatenate lists - so it breaks the rule of immediately returning a value. We then need to transform it so it can immediately return a value:
def reverse[A](input: List[A]):List[A] = {
@tailred
def go(rest: List[A], result: List[A]): List[A] = {
rest match {
case head :: tail => go(tail, head :: result)
case Nil => result
}
}
go(input, Nil)
}
Here you see that after recursive call go(tail, head :: result)
the only work to do is to return produced value immediately. Therefore it’s eligible for tail call optimization.
Another important thing in taill call optimization in Scala is that Scala compiler only transforms self-recursive tail calls, i.e. the tail call in a method must call that method itself. Scala compiler can’t optimize e.g. mutual tail calls as in this code:
def methodA(input: T): T = {
if (condition) methodB(input + 2) else input
}
def methodB(input: T): T = {
if (condition) methodA(input + 3) else input
}
Scala tail call optimization works by turning a method to a loop, e.g. from that code:
def method(p1: Int, p2: String, p3: Char): String = {
if (condition(p1)) {
transform(p2)
} else {
if (p3 == 'c') {
method(p1 + 2, p2, p3)
} else {
method(p1, p2, 'a')
}
}
}
is turned into that loop:
def method(_p1: Int, _p2: String, _p3: Char): String = {
// emulate parameter reassignment by copying them to variables first
var p1 = _p1
var p2 = _p2
var p3 = _p3
while (true) {
if (condition(p1)) {
// that's not a recursive call, so just break out of the loop
return transform(p2)
} else {
if (p3 == 'c') {
// emulate recursive call with new parameters values
p1 = p1 +2
p2 = p2
p3 = p3
// this is and end of loop body so next iteration will be the same as calling a method recursively
} else {
// emulate recursive call with new parameters values
p1 = p1
p2 = p2
p3 = 'a'
// this is and end of loop body so next iteration will be the same as calling a method recursively
}
}
}
}
I hope that makes it clear. You can always look at bytecode produced by Scala compiler to check what’s going on.