Kungfuice.com

Tail Recursive Algorithms In Scala

< ![endif]–>After the NFJS conference this weekend I have been spending more and more time working in Scala and trying to learn the ins-and-outs of the language.  One of the neat things I came across was tail recursive algorithm optimization within the language itself.

When writing in a functional language like Scala you rely heavily on recursive algorithms to do your work, instead of iterative algorithms more present in OO languages like Java. This leads to an interesting problem with running functional languages within the JVM.

The Java Virtual Machine does not have support for tail-recursive algorithm optimizations.  What does that mean? Basically the JVM cannot spot when to optimize calls stacks for recursive algorithms. Well who cares right? If you’re writing in Java this issue doesn’t usually come up since most of us simply write our loops and are happy with the performance the JVM offers us.

However, when you are writing a lot of recursive algorithms you quickly start to see how tail-recursive algorithms help makes your code more efficient.

For those of you who don’t remember what a tail-recursive algorithm is, here is a short little explanation:

“A Tail-recursive function is a function that ends in a recursive call to itself (effectively not building up any deferred operations). Tail recursive functions have the ability to re-use the same stack frame over and over and therefore are not bound by the number of available stack frames.  Many people have written the simple factorial function recursively, but many have noticed that if you pass it a value of N that is large enough you will see a dreaded Out of Memory exception.

The reason for this is due to the factorial functions deferred operation statement that comes at the end of the method. Let’s look at the simple factorial algorithm

1
2
3
4
5
6
7

//INPUT: n is an Integer such that n >= 1
int fact(int n) {
   if (n == 1)
      return 1;
   else
      return n* fact(n-1);
}

H You can see that at then end of the algorithm we have a deferred operation of multiplying n with the next value computed from factorial, this goes on and on until we finally hit a factorial function that returns one, at which point the stack is popped and everything returns nicely. However we are now bound by the available stack frames in terms of computing n (Also by the max size of an int, but that’s beside the point).

In a tail-recursive algorithm you do not see this deferred execution, and therefore the same stack frame can be reused over and over again. Here is the same algorithm rewritten using a tail-recursive algorithm.

1
2
3
4
5
6
7
8
9

//INPUT: n is an Integer such that n >= 1
int fact(int n) {
    return fact_support(n, 1);
}
 
int fact_support(int n, int acc) {
    if (n == 0) return acc;
    else return fact_support(n-1,acc*n);
}

As you can see there are no deferred operations in this example we have effectively gotten rid of having to use n number of stack frames. Each call to fact_support brings with it the current accumulated sum, and thus does not need to wait to “pop” the stack and rely on the stack pop to accumulate the sum of the factorials.

As you can see tail-recursive optimizations are very important to languages where recursion is relied on heavily. Without this type of optimization many of the recursive algorithms are now bound by the number of available stack frames.

So that can’t be so hard right? Why not just write all your algorithms to use tail-recursion? Well for one it’s not always possible to do this, but also it puts a lot of work in the hands of the developer. We have this beautiful thing called the JVM that should be able to spot cases where optimization can occur.

Unfortunately the JVM doesn’t know how to spot this optimization, therefore the Scala compiler must look at ways of optimizing your code. Even more unfortunate the Scala documentation explicitly states that you should not rely on the Scala compiler making this optimization.

It may optimize your code, but it may not as well, so really the only way to be sure is to write your algorithms guaranteeing that tail-recursion is being utilized from the get-go.

It would be really nice to see the JVM improved to allow for this type of optimization to be done in the Hotspot, and there has been talk about improving the JVM to support functional languages, but I guess time will only tell.