Tail recursion and transformations

Quite a few programs contain loops that account for a substantial portion of their total processing time. These loops will often iteratively update more than one variable, and the updates for each variable will often depend upon the values of the others.

When iterations are represented as tail-recursive functions, these variables will be represented as parameters to the functions. A quick reminder: a recursive call is tail recursive if the return value of that call is immediately returned as the value of the calling function; it isn't necessary to remember the context of the calling function when invoking the call.

Because of this attribute, there is a nice correspondence between tail-recursive functions and loops: each recursive call can be thought of simply as one more iteration through a loop. But because the variable parameter values are sent to the recursive call all at once, it is much easier to get the updated values right than it is in a loop. Furthermore, awkward break statements are often replaced by simple returns from the function.

But representing iteration this way in Java programming can be inefficient because numerous recursive calls risk overflowing the stack.

The solution is relatively simple: because these tail-recursive functions are really just easier ways of writing loops, have the compiler automatically transform them to loops. Then you get the best of both worlds.

But although it is well known how to automatically transform a tail-recursive function into a simple loop, the Java specification doesn't require that this transformation be made. Presumably, one reason it is not a requirement is that, in general, the transformation can't be made statically in an object-oriented language. Instead, the transformation from tail-recursive function to simple loop must be done dynamically by a JIT compiler.

To understand why this is the case, consider the following failed attempt to multiply the elements of an iterator over a collection of integers.

Because the following program contains a bug, it throws an exception when run. But, as many of the earlier articles in this column have demonstrated, the precise exception that a program throws is an invaluable clue as to where the bug in the program resides (as well as an excellent identifier for the type of bug), and we wouldn't want the compiler to alter the program in such a way that the resulting code throws a different exception.

import java.util.Iterator;

public class Example {

  public int product(Iterator i) {
    return productHelp(i, 0);
  }

  int productHelp(Iterator i, int accumulator) {
    if (i.hasNext()) {
      return productHelp(i, accumulator * ((Integer)i.next()).intValue());
    }
    else {
      return accumulator;
    }
  }
}

Notice the bug in the product method. It calls productHelp with an accumulator value of "0". It should be "1". Otherwise, a call to product on any instance of class Example will produce "0", regardless of the Iterator passed to it.

Suppose that this bug is eventually fixed, but, in the meantime, a subclass of class Example has been created, as shown in Listing 2:

import java.util.*;

class Example {

  public int product(Iterator i) {
    return productHelp(i, 1);
  }

  int productHelp(Iterator i, int accumulator) {
    if (i.hasNext()) {
      return productHelp(i, accumulator * ((Integer)i.next()).intValue());
    }
    else {
      return accumulator;
    }
  }
}

// And, in a separate file:

import java.util.*;

public class Example2 extends Example {
  int productHelp(Iterator i, int accumulator) {
    if (accumulator < 1) {
      throw new RuntimeException("accumulator to productHelp must be >= 1");
    }
    else {
      return super.productHelp(i, accumulator);
    }
  }

  public static void main(String[] args) {
    LinkedList l = new LinkedList();
    l.add(new Integer(0));
    new Example2().product(l.listIterator());
  }
}

The overridden productHelp method in class Example2 tries to catch such improper calls to productHelp by throwing a run-time exception if the accumulator is less than "1". Unfortunately, in doing so, it introduces a new bug. If the Iterator contains any instances of "0", then productHelp will crash on its own recursive call.

Now notice that, in the main method of class Example2, an instance of Example2 is created and its product method is called. Because the Iterator passed to this method contains a "0", the program should crash.

However, you can see that productHelp in class Example is strictly tail recursive. Suppose a static compiler were to convert the body of this method to a loop, as shown in Listing 3:

  int productHelp(Iterator i, int accumulator) {
    while (i.hasNext()) {
      accumulator *= ((Integer)i.next()).intValue();
    }
    return accumulator;
  }

Then the initial call to productHelp would result in a call to the super method. The super method would simply loop through the iterator to compute its result. No exception would be thrown.

Imagine how confusing it would be to compile this code with two different static compilers, only to find that the resulting code threw an exception in one case and not in the other.

Back to top

Will your JIT do the job?

So, as the example in Listing 3 shows, we cannot expect static compilers to perform transformation of tail recursion on Java code while preserving the semantics of the language. Instead, we must rely on dynamic compilation by the JIT. Depending on the JVM, the JIT may or may not do this.

One way to check whether your JIT transforms your tail-recursive methods is to compile and run the following small test class:

public class TailRecursionTest {

  private static int loop(int i) {
    return loop(i);
  }

  public static void main(String[] args) {
    loop(0);
  }
}

Let's consider for a moment the loop method in this class. This method will simply call itself recursively for as long as it can. Because it will never return, and it doesn't affect any outside variables in any way, replacing its body as shown in Listing 5 preserves the semantics of the program:

public class TailRecursionTest {

  private static int loop(int i) {
    while (true) {
    }
  }

  public static void main(String[] args) {
    loop(0);
  }
}

And, in fact, this is exactly the transformation that a sufficiently sophisticated compiler would make.

If your JIT compiler converts tail-recursive calls to iteration, this program will continue to run indefinitely. Its memory requirements are small and they don't grow with time.

On the other hand, if the JIT doesn't make this transformation, the program will quickly exhaust the stack space and report a stack overflow error.

I ran this program with a couple of the Java SDKs, and the results were surprising. Running on Sun's Hotspot JVM for version 1.3 reveals that Hotspot doesn't perform the transformation. At default settings, the stack space is exhausted in less than a second on my machine.

On the other hand, IBM's JVM for version 1.3 purrs along without a problem, indicating that it does transform the code in this way.

Back to top

Wrapup

Remember: we can't rely on our code to always be running on a JVM that will transform tail-recursive calls. Therefore, to guarantee reasonable performance across JVMs, you should always try to write code that most naturally fits a tail-recursive pattern in an iterative style instead.

But be careful. As our example demonstrates, it is very easy to introduce bugs by transforming code in this way, whether it is altered by human hands or by software.

Resources

• For more information on Hotspot, check out Sun's documentation on it.
  
  
  
  
• Give the IBM developer kit for Java version 1.3 a try. I predict you'll be pleased with the performance.
  
  
  
  
• For a good discussion of tail recursion and its conversion to iteration, check out the CMU Common Lisp User's Manual. Although the manual is, of course, written for Common Lisp, the discussion on tail recursion is applicable to other languages, including the Java language.
  
  
  
  
• Read Eric's complete series on diagnosing Java code.
  
  

About the author

Rate this article

Comments

Back to top

Table of contents

• Tail recursion and transformations
• Will your JIT do the job?
• Wrapup
• Resources
• About the author
• Comments