7.5 Recursion

Recursive algorithms are used because they're often clearer and more elegant than the alternatives, and therefore have a lower maintenance cost than the equivalent iterative algorithm. However, recursion often (but not always) has a cost; recursive algorithms are frequently slower. So it is useful to understand the costs associated with recursion and how to improve the performance of recursive algorithms when necessary.

Recursive code can be optimized by a clever compiler (as is done with some C compilers), but only if presented in the right way (typically, it needs to be tail-recursive: see the sidebar Tail Recursion). For example, Jon Bentley^[3] found that a functionally identical recursive method was optimized by a C compiler if he did not use the ? : conditional operator (using if statements instead). However, it was not optimized if he did use the ?: conditional operator. He also found that recursion can be very expensive, taking up to 20 times longer for some operations that are naturally iterative. Bentley's article also looks briefly at optimizing partial-match searching in ternary search trees by transforming a tail recursion in the search into an iteration. See Chapter 11 for an example of tuning a ternary search tree, including an example of converting a recursive algorithm to an iterative one.

^[3] "The Cost of Recursion," Dr. Dobb's Journal, June 1998.

public static long factorial1(int n)
{
  if (n < 2) return 1L;
  else return n*factorial1(n-1);
}

public static long factorial1a(int n)
{
  //NOT recursive. Sets up the tail-recursive call to factorial1b(  )
  if (n < 2) return 1L;
  else return factorial1b(n, 1L);
}
public static long factorial1b(int n, long result)
{
  //No need to consider n < 2, as factorial1a handles that
  if (n =  = 2) return 2L*result;
  else return factorial1b(n-1, result*n);
}

Generally, the advice for dealing with methods that are naturally recursive (because that is the natural way to code them for clarity) is to go ahead with the recursive solution. You need to spend time counting the cost (if any) only when your profiling shows that this particular method call is a bottleneck in the application. At that stage, it is worth pursuing alternative implementations or avoiding the method call completely with a different structure.

In case you need to tune a recursive algorithm or convert it into an iterative one, I provide some examples here. I start with an extremely simple recursive algorithm for calculating factorial numbers, as this illustrates several tuning points:

public static long factorial1(int n)
{
  if (n < 2) return 1L;
  else return n*factorial1(n-1);
}

I have limited the function to long values, which means that you cannot use the function beyond factorial 20, as that overflows the long data type. This keeps the function simple for this illustration.

Since this function is easily converted to a tail-recursive version, it is natural to test the tail-recursive version to see if it performs any better. For this particular function, the tail-recursive version does not perform any better, which is not typical. Here, the factorial function consists of a very simple fast calculation, and the extra function-call overhead in the tail-recursive version is enough of an overhead that it negates the benefit that is normally gained.

Let's look at other ways this function can be optimized. Start with the classic conversion for recursive to iterative and note that the factorial method contains just one value that is successively operated on to give a new value (the result), along with a parameter specifying how to operate on the partial result (the current input to the factorial). A standard way to convert this type of recursive method is to replace the parameters passed to the method with temporary variables in a loop. In this case, you need two variables, one of which is passed into the method and can be reused. The converted method looks like:

public static long factorial2(int n)
{
  long result = 1;
  while(n>1)
  {
    result *= n--;
  }
  return result;
}

Measuring the performance, you see that this method calculates the result in 92% of the time taken by the original recursive factorial1( ) method (using the JDK 1.2.2 results;^[4] see Table 7-3.

^[4] The 1.4.0 server HotSpot VM optimized the recursive version sufficiently to make it faster than the iterative version.

The recursion-to-iteration technique as illustrated here is general, and another example in a different domain may help make this generality clear. Consider a linked list, with singly linked nodes consisting of a next pointer to the next node, and a value instance variable holding (in this case) just an integer. A simple linear search method to find the first node holding a particular integer looks like:

Node find_recursive(int i)
{
  if (node.value =  = i)
    return node;
  else if(node.next != null)
    node.next.find_recursive(i);
  else
    return null;
}

To convert this to an iterative method, use a temporary variable to hold the "current" node, and reassign that variable with the next node in the list at each iteration. The method is clear, and its only drawback compared to the recursive method is that it violates encapsulation (this one method directly accesses the instance variable of each node object):

Node find_iterative(int i)
{
  Node node = this;
  while(node != null)
  {
    if (node.value =  = i)
      return node;
    else
      node = node.next;
  }
  return null;
}

Before looking at general techniques for converting other types of recursive methods to iterative ones, I will revisit the original factorial method to illustrate some other techniques for improving the performance of recursive methods.

To test the timing of the factorial method, I put it into a loop to recalculate factorial(20) many times. Otherwise, the time taken is too short to be reliably measured. When this situation is close to the actual problem, a good tuning technique is to cache the intermediate results. This technique can be applied when some recursive function is repeatedly being called and some of the intermediate results are repeatedly being identified. This technique is simple to illustrate for the factorial method:

public static final int CACHE_SIZE = 15;
public static final long[  ] factorial3Cache = new long[CACHE_SIZE];
  
public static long factorial3(int n)
{
  if (n < 2) return 1L;
  else if (n < CACHE_SIZE)
  {
    if (factorial3Cache[n] =  = 0)
      factorial3Cache[n] = n*factorial3(n-1);
    return factorial3Cache[n];
  }
  else return n*factorial3(n-1);
}

With the choice of 15 elements for the cache, the factorial3( ) method takes 56% of the time taken by factorial1( ). If you choose a cache with 21 elements, so that all except the first call to factorial3(20) are simply returning from the cache with no calculations at all, the time taken is just 8% of the time taken by factorial1( ) (using the JDK 1.2 results; see Table 7-3).

In this particular situation, you can make one further improvement, which is to compile the values at implementation and hardcode them in:

public static final long[  ] factorial4Cache = {
  1L, 1L, 2L, 6L, 24L, 120L, 720L, 5040L, 40320L, 362880L, 3628800L,
  39916800L, 479001600L, 6227020800L, 87178291200L};
public static final int CACHE_SIZE = factorial4Cache.length;
public static long factorial4(int n)
{
  if (n < CACHE_SIZE)
    return factorial4Cache[n];
  else return n*factorial4(n-1);
}

This is a valid technique that applies when you can identify and calculate partial solutions that can be included with the class at compilation time.^[5]

^[5] My editor Mike Loukides points out that a variation on hardcoded values, used by state-of-the-art high-performance mathematical functions, is a partial table of values together with an interpolation method to calculate intermediate values.