4.4: Implementing Recursive Programs

Recursion is a powerful tool for the development of algorithms and leads to concise, clear recursive programs that can be easier to check for correctness. Complex algorithms may be expressed using relatively few program statements, which at the same time emphasize the structure of the algorithm. This will become even more apparent later in the text, as more difficult problems are solved.

A function that invokes itself is directly recursive. A function is indirectly recursive if any sequence of calls to other functions can lead to a call to the original function. Compilers for recursive languages must translate recursive as well as nonrecursive programs. It is not necessary to understand how a recursive program is translated (any more than it is necessary to know how a nonrecursive program is translated) in order to understand or to write the program itself. But it is necessary to know how the program will execute. This amounts to being able to simulate its execution.

The programmer constrained to a nonrecursive language can still use the power of recursion. This is done by writing a program as if the language allowed recursion, and then translating the program into an equivalent nonrecursive program. This is what compilers for recursive languages do and is one reason for spending time finding out how to translate (or implement) a recursive program.

As shown in the discussion of Counting Squares, some problems should not be solved using recursion under any circumstances. Sometimes, as in the Towers of Hanoi problem, we may only be able to think of a recursive solution. Often we can find both a recursive and a nonrecursive solution, which may be compared for trade-offs in clarity, conciseness, storage, and execution time.

Even though a recursive solution may not be best, it may suggest an approach to the problem that otherwise might have been missed and that may turn out to be the most desirable. In fact, the translated version of a recursive solution can often be helpful in finding desirable modifications. This is another reason for looking at the translation process.

Normally, if a recursive approach is right for a problem, and is applied intelligently, further refinements of the program do not improve its efficiency significantly. Breaking up a problem as required by the recursive approach does, however, create the possibility of doing certain tasks in parallel. For instance, the three components of the Towers of Hanoi solution may all be done at the same time with parallel processing. Languages and computer systems that allow concurrent processing will surely become more prevalent. When they do, recursive solutions will have another advantage.

If each successive call to a recursive function were implemented so that during execution a new copy of the function is created with its own storage for the return and its scratchpad values, then, in effect, the function could be treated like any function in a nonrecursive program. With the advent of cheaper and larger storage, this may well occur in the future, but until then, another means of managing the generated returns and scratchpad values is needed.

The essential difference between nonrecursive (or iterative) programs and recursive programs is the storage needed for the returns and scratchpad values of the latter. Figures 4.2, 4.4, and 4.6 actually represent the bookkeeping needed to simulate the execution of a recursive program. The basic idea in translating such programs is to implement this bookkeeping procedure as follows:

1. Each time a recursive call is made to the function,

a. save the proper return place and the current scratchpad values,

b. set the scratchpad values to their new values.

2. Each time a recursive call is completed,

a. restore the current return and scratchpad values to those that were last saved (and save them no longer),

b. return to the proper place in the recursive function, or to the original calling component if it is the initial call that has just finished.

This procedure does not apply to a function that returns a value, but it may be modified to do so. Or the function may be modified to return the value in an additional parameter passed by pointer. As an illustration of this, the first version of copy might be obtained by such a modification of the second.

Notice that the information to be retained (return and scratchpad values) must be recalled in the order opposite to the order in which it is generated. This is no different for nonrecursive programs, except that then the information is saved locally with each component. It is helpful to think of return and scratchpad values as the entries of a record. Then the collection of records corresponding to each suspended recursive call must be stored in some data structure. The data structure must retain not only these records, but also the correct order.

In step 1 above, the record to be saved must become the new first record in the order. In step 2, the current first record (the last saved) must be removed from the data structure. A data structure for storing information so that new information can be inserted, so that a deletion always removes the last piece of information inserted, and which can be tested to see if it is empty (contains no information) is called a stack. Stacks will be discussed in more detail later in the chapter; for now they will simply be used.

4.4.1 A Sample Implementation of Towers

4.4.2 A Sample Implementation for Permutations