17.2. Recursion

In recursion, a routine solves a small part of a problem itself, divides the problem into smaller pieces, and then calls itself to solve each of the smaller pieces. Recursion is usually called into play when a small part of the problem is easy to solve and a large part is easy to decompose into smaller pieces.

Recursion isn't useful often, but when used judiciously it produces elegant solutions, as in this example in which a sorting algorithm makes excellent use of recursion:

Java Example of a Sorting Algorithm That Uses Recursion

 void QuickSort( int firstIndex, int lastIndex, String [] names ) {    if ( lastIndex > firstIndex ) {       int midPoint = Partition( firstIndex, lastIndex, names );       QuickSort( firstIndex, midPoint-1, names );       <-- 1       QuickSort( midPoint+1, lastIndex, names )       <-- 1    } } 

(1)Here are the recursive calls.

In this case, the sorting algorithm chops an array in two and then calls itself to sort each half of the array. When it calls itself with a subarray that's too small to sort such as ( lastIndex <= firstIndex ) it stops calling itself.

For a small group of problems, recursion can produce simple, elegant solutions. For a slightly larger group of problems, it can produce simple, elegant, hard-to-understand solutions. For most problems, it produces massively complicated solutions in those cases, simple iteration is usually more understandable. Use recursion selectively.

Example of Recursion

Suppose you have a data type that represents a maze. A maze is basically a grid, and at each point on the grid you might be able to turn left, turn right, move up, or move down. You'll often be able to move in more than one direction.

How do you write a program to find its way through the maze, as shown in Figure 17-1? If you use recursion, the answer is fairly straightforward. You start at the beginning and then try all possible paths until you find your way out of the maze. The first time you visit a point, you try to move left. If you can't move left, you try to go up or down, and if you can't go up or down, you try to go right. You don't have to worry about getting lost because you drop a few bread crumbs on each spot as you visit it, and you don't visit the same spot twice.

Figure 17-1. Recursion can be a valuable tool in the battle against complexity when used to attack suitable problems

The recursive code looks like this:

C++ Example of Moving Through a Maze Recursively

bool FindPathThroughMaze( Maze maze, Point position ) {    // if the position has already been tried, don't try it again    if ( AlreadyTried( maze, position ) ) {       return false;    }    // if this position is the exit, declare success    if ( ThisIsTheExit( maze, position ) ) {       return true;    }    // remember that this position has been tried    RememberPosition( maze, position );    // check the paths to the left, up, down, and to the right; if    // any path is successful, stop looking    if ( MoveLeft( maze, position, &newPosition ) ) {       if ( FindPathThroughMaze( maze, newPosition ) ) {          return true;       }    }    if ( MoveUp( maze, position, &newPosition ) ) {       if ( FindPathThroughMaze( maze, newPosition ) ) {          return true;       }    }    if ( MoveDown( maze, position, &newPosition ) ) {       if ( FindPathThroughMaze( maze, newPosition ) ) {          return true;       }    }    if ( MoveRight( maze, position, &newPosition ) ) {       if ( FindPathThroughMaze( maze, newPosition ) ) {          return true;       }    }    return false; }

The first line of code checks to see whether the position has already been tried. One key aim in writing a recursive routine is the prevention of infinite recursion. In this case, if you don't check for having tried a point, you might keep trying it infinitely.

The second statement checks to see whether the position is the exit from the maze. If ThisIsTheExit() returns true, the routine itself returns true.

The third statement remembers that the position has been visited. This prevents the infinite recursion that would result from a circular path.

The remaining lines in the routine try to find a path to the left, up, down, and to the right. The code stops the recursion if the routine ever returns true that is, when the routine finds a path through the maze.

The logic used in this routine is fairly straightforward. Most people experience some initial discomfort using recursion because it's self-referential. In this case, however, an alternative solution would be much more complicated and recursion works well.

Tips for Using Recursion

Keep these tips in mind when using recursion:

Make sure the recursion stops Check the routine to make sure that it includes a nonrecursive path. That usually means that the routine has a test that stops further recursion when it's not needed. In the maze example, the tests for AlreadyTried() and ThisIsTheExit() ensure that the recursion stops.

Use safety counters to prevent infinite recursion If you're using recursion in a situation that doesn't allow a simple test such as the one just described, use a safety counter to prevent infinite recursion. The safety counter has to be a variable that's not re-created each time you call the routine. Use a class member variable or pass the safety counter as a parameter. Here's an example:

Visual Basic Example of Using a Safety Counter to Prevent Infinite Recursion

 Public Sub RecursiveProc( ByRef safetyCounter As Integer )       <-- 1    If ( safetyCounter > SAFETY_LIMIT ) Then       Exit Sub    End If    safetyCounter = safetyCounter + 1    ...    RecursiveProc( safetyCounter ) End Sub

(1)The recursive routine must be able to change the value of safetyCounter, so in Visual Basic it's a ByRef parameter.

In this case, if the routine exceeds the safety limit, it stops recursing.

If you don't want to pass the safety counter as an explicit parameter, you could use a member variable in C++, Java, or Visual Basic, or the equivalent in other languages.

Limit recursion to one routine Cyclic recursion (A calls B calls C calls A) is dangerous because it's hard to detect. Mentally managing recursion in one routine is tough enough; understanding recursion that spans routines is too much. If you have cyclic recursion, you can usually redesign the routines so that the recursion is restricted to a single routine. If you can't and you still think that recursion is the best approach, use safety counters as a recursive insurance policy.

Keep an eye on the stack With recursion, you have no guarantees about how much stack space your program uses and it's hard to predict in advance how the program will behave at run time. You can take a couple of steps to control its run-time behavior, however.

First, if you use a safety counter, one of the considerations in setting a limit for it should be how much stack you're willing to allocate to the recursive routine. Set the safety limit low enough to prevent a stack overflow.

Second, watch for allocation of local variables in recursive functions, especially memory-intensive objects. In other words, use new to create objects on the heap rather than letting the compiler create auto objects on the stack.

Don't use recursion for factorials or Fibonacci numbers One problem with computer-science textbooks is that they present silly examples of recursion. The typical examples are computing a factorial or computing a Fibonacci sequence. Recursion is a powerful tool, and it's really dumb to use it in either of those cases. If a programmer who worked for me used recursion to compute a factorial, I'd hire someone else. Here's the recursive version of the factorial routine:

Java Example of an Inappropriate Solution: Using Recursion to Compute a Factorial

int Factorial( int number ) {    if ( number == 1 ) {       return 1;    }    else {       return number * Factorial( number - 1 );    } }

In addition to being slow and making the use of run-time memory unpredictable, the recursive version of this routine is harder to understand than the iterative version, which follows:

Java Example of an Appropriate Solution: Using Iteration to Compute a Factorial

int Factorial( int number ) {    int intermediateResult = 1;    for ( int factor = 2; factor <= number; factor++ ) {       intermediateResult = intermediateResult * factor;    }    return intermediateResult; }

You can draw three lessons from this example. First, computer-science textbooks aren't doing the world any favors with their examples of recursion. Second, and more important, recursion is a much more powerful tool than its confusing use in computing factorials or Fibonacci numbers would suggest. Third, and most important, you should consider alternatives to recursion before using it. You can do anything with stacks and iteration that you can do with recursion. Sometimes one approach works better; sometimes the other does. Consider both before you choose either one.