Java – Does java support and optimize away tail-recursive calls

javajvmoptimizationrecursionscala

Say I got a recursive function that is tail recursive. I wonder if this function will be implemented as recursion, growing on the stack, or will it be changed to a loop (since it is a tail-recursive function)?

I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?

Best Answer

Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)

But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.

Look at this:

int sum(List<Integer> integers) {
    return sum(integers, 0);
}

int sum(List<Integer> integers, int sumSoFar) {
    if (integers.isEmpty())
        return sumSoFar;
    else
        return sum(
                integers.subList(1, integers.size()),
                sumSoFar + integers.get(0)
        );
}

See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.

In your snippet the stack frame would probably have to exist as long as the recursive call..

Related Topic