Tail Recursive Algorithms In Scala

Posted by & filed under Computers, java, programming.

< ![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

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

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

6 Responses to “Tail Recursive Algorithms In Scala”

  1. Dan Hodge

    An excellent discussion of tail recursion and much easier to follow than the section on tail recursion in Scala By Example.

  2. kungfuice

    I’m glad this helped you out. Keep an eye out for some more Scala posts I’ll be making in the next couple of weeks.

    Chris

  3. Paul Copeland

    Even though there is no “deferred execution” there are the same number of nested function calls and presumably the same depth of the stack in the second case unless the system does some kind of rewriting. The usual examples show that tail recursion can always be rewritten by the programmer with a loop. Many useful recursive algorithms cannot be reduced to tail recursion and there is no simple way to remove the recursion.

  4. Bill Allen

    The whole point of the tail recursion optimization is that the compiler removes the function calls effectively rewriting the algorithm to be an efficient loop.

  5. Amal

    I am just trying to make sure that I get it right. You meant by the optimization that it can reuse the stack frame over and over, right?. But you mentioned that it does not always detect that optimization even if the program was written as tail recursive?

  6. kungfuice

    @Amal This is true. Since the Java Virtual Machine has no way of optimizing tail recursive functions it is solely up to the Scala compiler to detect tail call recursive functions and reorder them into iterative functions. Unfortunately if you do anything fancy in your tail-recursion. Basically any function that ends in an indirect function call. Really tail-call optimization in Scala is limited to any function that calls itself (and only itself) directly as its last operation, without going through a function value.