Blog
Functional Programming
Scala: Tail Recursion Optimisation and comparison to Java

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

It depends completely on the compiler i.e. whether the compiler is really optimising the byte code for tail recursion functions or not.

Let us consider our plain old factorial program using Scala.

Following Scala code calculates the factorial in tail recursion process:

Tail Recursion

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:

Tail Recursion

This will generate the factorial.class file.

Now we will use the following command to see the byte code of the class file generated above:

Tail Recursion

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

Tail Recursion

(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. So that signifies that for each recursive call the calculate method is getting called which in turn increasing the call stack in the memory.

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

Why?

Let us re-write factorial code as below:

Tail Recursion

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 below:

Tail Recursion

We can see that the above byte code is never calling the calculate method, instead it is calling the same instructions in a loop. So 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.

Now we can say that the Scala compiler has optimised the tail recursive function.

But why is the difference? Scala compiler will optimise any tail recursion function only if it is sure that the same function will not be overridden. Since 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 to be overridden; but this will also reduce the scope of that function. So whether to make it final or private will depend on the design of our code.

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

Tail Recursion

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

Tail Recursion

This clearly indicates the reason why the Scala compiler didn`t optimised the calculate method in the first code snippet. If we remove the @tailrec annotation, Scala compiler will generate non-optimised 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:

Tail Recursion

Here we have added the final keyword again to ensure that it cannot overridden in the sub classes.

Let us compile the above Java class:

Tail Recursion

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

Tail Recursion

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 optimised 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.

So this signifies that whatever may be the method declaration Java compiler will not optimise tail recursive method. Whereas Scala compiler will optimise the same if the method is declared as final or private.

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

 

Dipta P. Banerjee

Comment(s)
Name :
Email :
Comment :