Scala: Tail Recursion Optimization and comparison to Java

Tail Recursion is supposed to be a better method than normal recursion methods, but does that help in the actual execution of the method? We can only say yes if the recursion actually does not increase the call stack in memory and instead re-uses it.

It depends completely on the compiler i.e. whether the compiler is really optimizing the byte code for tail recursion functions or not. Let us consider our plain old factorial program using Scala.

The following Scala code calculates the factorial in tail recursion process:

STR_1

Let us examine the byte code generated by Scala compiler for the above Scala class. We write the above Scala code in a file, say “factorial.scala” and compile it using the command:

STR_2

This will generate the factorial.class file. We will now use the following command to inspect the byte code of the class file generated above:

STR_3

This will give the byte code of the factorial.class which will look something like below:

STR_4

(For details of the above JVM instruction set please refer to the Online Instruction Reference)

If we closely look into the byte code above, we will see that the calculate method is again calling itself – the invokevirtual #12 is actually calling the calculate method repeatedly for each recursion. This signifies that for each recursive call the calculate method is getting called which is in turn increasing the call stack in the memory.

So ideally we are not getting any advantage of tail recursion optimization even though Scala claims that it optimizes tail recursive function.

Why?

Let us re-write factorial code as below:

STR_5

Here we have added the final keyword before the method definition of the calculate method. We all know that adding the final keyword prevents this method to be overridden in the sub classes.

Now if we compile the above class and see the byte code, it will look something like this:

STR_6

We can see that the above byte code is never calls the calculate method, instead it calls the same instructions in a loop. This signifies that for the recursive call the same method calculate is not getting called repeatedly, thus not increasing the call stack in the memory.

We can say now that the Scala compiler has optimized the tail recursive function.

But what is the reason for this difference? Scala compiler will optimize any tail recursion function only if it is sure that the same function will not be overridden. After all, any sub class which overrides the function can change the implementation to a non-tail recursive code. Here we have achieved this by adding the final keyword. The other possible way is to make the function private, which will also prevent the function from being overridden; but this will also reduce the scope of that function. So, the decision to make it final or private will depend on the design of our code.

To ensure that compiler optimizes the tail recursive function, we can add @tailrec annotation to the function which we want the compiler to optimize. The code will look something like below:

STR_7

In the above code if we remove the final keyword and try to compile the code using scalac we will get the following compilation error:

STR_8

This clearly indicates the reason why the Scala compiler did not optimize the calculate method in the first code snippet. If we remove the @tailrec annotation, Scala compiler will generate non-optimized byte code which it did in our initial code at the beginning.

Now what about Java? We can write the same factorial code in Java using tail recursive function as follows:

STR_9

Here we have added the final keyword again to ensure that it cannot be overridden in the sub classes. Let us compile the above Java class:

STR_10

If we investigate the byte code generated for the above Java class using the javap command we will get something like:

STR_11

Here we can see that the generated byte code calls the calculate method for each recursion which is similar to the one generated by the Scala compiler in our first example. So the generated byte code is not optimized for the tail recursive method and in turn increases the call stack in memory. Even if we remove the final keyword from the calculate method in the Java class and generate the byte code we will see the same result.

This signifies that whatever may be the method declaration, Java compiler will not optimize a tail recursive method. Whereas Scala compiler will optimize the same if the method is declared as final or private.

We can thus say that a Tail Recursive function has no effect on performance in Java, whereas Scala compiler will optimize tail recursive functions based on the condition that the code ensures that function is not overridden in sub classes.

Author: Dipta P. Banerjee