Gary Syck is a programmer for Crystal Point in Botholl, Washington. He has 10 years programming experience, including seven years in C. You can contact him at 12032 100th Ave. NE, #D203, Kirkland, WA 98034.
Recursion is a powerful tool for the algorithm designer. The idea is to break a large task down into a number of identical sub-tasks and have the recursive routine call itself for each sub-task. This tool simplifies tasks such as reading all of the files on an MS-DOS system. Instead of trying to come up with a routine that visits all of the sub-directories, you just develop a routine to read a single directory that calls itself whenever a directory item is a sub-directory. What once was a large task is now a manageable one. In this article, I will demonstrate how to create recursive algorithms and then convert them to non-recursive routines to avoid some of the problems with implementing recursive routines on microcomputers.
When designing a recursive algorithm, you must first ask yourself if the task can be broken down into a number of identical sub-tasks. Next, determine under what conditions the recursive routine exits. Knowing these conditions is important, since the routine must not only exit from any given instance but must also exit from all previous instances. Later in this article you will see two examples of how to develop recursive algorithms.
Recursion loses some of its appeal in actually implementing the routine. Some languages do not allow recursion at all. Others such as C give you just enough rope to get yourself into trouble. The source of this trouble is often related to stack usage. Each time the recursive routine calls itself, it must save any registers it uses and the return address on the stack. Then the new instance of the routine makes room for a fresh copy of all of its local variables on the stack.
Consider the directory reading example previously mentioned. If the program is compiled using the large model, a string pointer argument (the path to read) takes eight bytes. This routine uses stack space to hold directory entries (32 bytes) and miscellaneous variables to keep track of the search (say eight bytes each). The total stack usage is 48 bytes for each call. If you call this routine from deep within a program that has little stack space to begin with (for example a TSR), you will get some interesting errors as the stacks grows up into whatever precedes it.
To show how to design recursive algorithms, this article presents two recursive routines. Once the routines are designed and coded in a recursive fashion, you can look at how to make them non-recursive to keep stack usage under control. After that you can compare the recursive and non-recursive versions to determine the possible benefits of this approach.
The first routine is for searching binary trees. In this case the tree is arranged such that the left child of any node is less than the root and the right child is greater than the root. The goal of the routine is to locate a specific value in the tree. This problem can easily be broken down into identical sub-tasks, each of which compares the value to find with a node. If the value to find is less than the node, get the left child. Otherwise, get the right child. The routine calls itself with each new node, until it finds a node without the required child, or it finds one that matches the value.
Listing 1 shows this algorithm coded in C. There are two cases to check to see if the routine should return. The first is if the value being tested matches the value for the node. In this case the search is successful and the routine returns the node number. The other case is if the required child node does not exist. This indicates that the value is not in the tree so the routine returns a --1. Each instance of the routine returns the result of the child instances until the value is finally returned to the original calling routine.
The next routine shows how to use recursion to sort a list of items. This is the well-known quicksort algorithm. It works by dividing the list into two parts. The parts are arranged such that all of the items in the first part are less than all of the items in the second part. Then, each of the parts are subjected to the same procedure. Eventually, the part is a single item so it must be sorted. The use of recursion in this algorithm is obvious: the routine need only make the two parts, then call itself twice, once for each part.
The tricky part of this algorithm is to make the two parts in the first place. Many techniques have been proposed, but the actual technique used is not important for this article. Listing 2 shows an implementation of the quicksort algorithm that uses a technique from Sedgewick.
Both of these routines handle a difficult problem efficiently. The tree search routine can find an item in a large tree with very few compares. The quicksort algorithm out-performs many other sort techniques for sorting randomly ordered data sets. One bottleneck common to both of these routines is the overhead required to do the recursion.
The tree search routine must do a function call for each node that it visits. In addition, once the desired node is found, it must do a number of returns to get that information back to the calling routine. Stack usage for this routine depends on how "balanced" the tree is. If the tree is perfectly balanced (all nodes without children are in the last row), the number of visits to find any given node is less than log2 of the size of the tree. For a 65,536 node tree, fewer than 16 visits are required. The impact on the stack in this case is minimal. On the other hand, in a worst-case unbalanced tree the routine may need to visit every node in the tree to find a node. In this case you may need more than the available stack space to run this routine.
Since the quicksort algorithm divides the list into two parts, it has the same stack usage properties as the binary tree search. If the routine to divide the list into two parts divides the parts evenly, there will not be many recursive calls. To make the partitioning routine efficient, it rarely divides the list evenly. As with the binary search, this routine may make as many recursive calls as there are items in the list.
Both of these routines can be converted to non-recursive versions that remove the overhead of the recursive calls. In both examples, removing recursion improves the execution speed of the routine. In the tree search routine it also removes the requirement for extra memory for each instance of the routine.
A recursive call accomplishes two tasks. First, it changes the arguments for the next instance. Second, it returns to the beginning of the routine. You can change the arguments by modifying the formal parameters. In the tree search routine this means setting NodeNumb to the number of the next node to look at. You can use a goto command to get back to the beginning of the routine.
Next, the exit condition needs to be changed. The return statements in the recursive version of a routine must be changed to a goto to the instruction past the recursive call. When there is more than one recursive call, you need a flag to show which call to jump past. When this is done to the tree search routine, you can easily see the advantages of the non-recursive routine. Since there is only one instance, there is no need to pass the final result up through previous instances. The routine can immediately return to the caller with the result.
Once the recursive routine has been converted, you may want to examine it to see if it can be cleaned up a bit. Listing 3 shows the tree search routine after it has been cleaned up. The first step was to notice that the two calls could be combined into a single goto with different values in NodeNumb. After that change, the routine looked like a while loop that exits with a null node or a matching node. Using a while statement gets rid of the gotos and results in an elegant non-recursive routine.
Complications come about when converting the quicksort routine. After the recursive call to divide the first half, you have to make another call to divide the second half. Of course, the first half, in turn, has a first and second half. The question is, "Where do you store the variables that define the halves?" The answer is to make a stack, and push the beginning and end of each half left to sort onto the stack. The routine is finished when the stack is exhausted.
If you have to make a stack to eliminate recursion, what is the advantage? The first advantage is that this stack can hold more halves than the recursive stack because there are no stack frames on it. The other advantage is that you can monitor the amount of data in the stack and use a different strategy when it gets full.
Listing 4 shows the modified quicksort routine. It pushes the beginning and end of each half to sort on the stack, then pops one half off the stack before looping back to the beginning. In this case, the loop with gotos resembles a do..while loop that exits when there are no items left in the stack. There is also logic to determine when the stack is full. If the stack is full, the quicksort routine calls a shell sort routine to sort the section.
In both the tree search routine and the quicksort, removing recursion makes a more efficient routine by eliminating time-consuming function calls. In addition, it eliminates the danger of stack overflow. If these routines are going to be part of a library, you should use the non-recursive versions.
Some algorithms would be difficult or impossible to discover if recursion were not available. The algorithm designer must consider recursion as a possible solution for any problem that could be divided into smaller parts. Once a recursive algorithm has been found, you can use the techniques demonstrated in this article to convert it to a more efficient and less dangerous, non-recursive routine.