Tail recursion optimization will not work with recursive invocations inside for
loop, because for
loop here is just a syntactic sugar for calling foreach
higher-order method. So, your code is equivalent to:
@tailrec
def shiftDown2(x: Int, bound: Int) {
val childOfX = chooseChild(x, bound)
childOfX.foreach { child =>
swap(x, child)
shiftDown2(child, bound)
}
}
scalac
can optimize tail calls only if recursive method is tail-calling itself directly - by translating it into something similar to while
loop in bytecode.
Unfortunately, this is not the case here - shiftDown2
calls childOfX.foreach
passing it an anonymous function. Then, foreach
(potentially) calls apply
on that anonymous function and that anonymous function finally calls shiftDown2
again. So this is an indirect recursion and cannot be optimized by scalac
. This limitation has its roots in the JVM, which doesn't have native tail call support.