When Not to Use Recursion

Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms. This does not mean, however, that such recursive definitions guarantee that a recursive algorithm is the best way to solve the problem. In fact, the explanation of the128 concept of recursive algorithm by such inappropriate examples has been a chief cause of creating widespread apprehension and antipathy toward the use of recursion in programming, and of equating recursion with inefficiency. This happened in addition to the fact that the widespread programming language FORTRAN forbids the recursive use of subroutines, thus preventing the invention of recursive solutions even when they are appropriate.

Programs in which the use of algorithmic recursion is to be avoided can be characterized by a schema which exhibits the pattern of their composition. The schema is that of (3.6) and, equivalently, of (3.7).

These schemata are natural in those cases in which values are to be computed that are defined in terms of simple recurrence relations. Let us look at the well-known example of the factorial numbers f, = i!:

The “zeroth” number is explicitly defined as f; = 1, whereas the subsequent numbers are usually defined—recursively—in terms of their predecessor:

This formula suggests a recursive algorithm to proceed to the nth factorial number. If we introduce the two variables J and F to denote the values i and f, at the ith level of recursion, we find the computation necessary to proceed to the next numbers in the sequences (3.8) to be

The first line of (3.11) is expressed in terms of our conventional programming notation as

A more frequently used, but essentially equivalent, form is the one given in (3.13). P is replaced by a so-called function procedure, i.e., a procedure with which a resulting value is explicitly associated, and which therefore may be used directly as a constituent of expressions. The variable F thereby129 becomes superfluous; and the role of J is taken by the explicit procedure parameter.

It is quite plain that in this case recursion can be replaced by simple iteration, namely, -by the program

In general, programs corresponding to the general schemata (3.6) or (3.7) should be transcribed into one according to schema (3.15)

There are also more complicated recursive composition schemes that can and should be translated into an iterative form. An example is the computation of the Fibonacci numbers which are defined by the recurrence relation

Computation of fib, by a call Fib(n) causes this function procedure to be activated recursively. How often? We notice that each call with n > 1 leads to 2 further calls, i.e., the total number of calls grows exponentially (see Fig. 3.2). Such a program is clearly impractical.

However, it is plain that the Fibonacci numbers can be computed by an iterative scheme that avoids the recomputation of the same values by use of auxiliary variables such that x = fib, and y = fib,_,.

(Note that the three assignments to x, y, z may be expressed by merely two assignments without need for the auxiliary variable z: x:= x+y;

Thus, the lesson to be drawn is to avoid the use of recursion when there is an obvious solution by iteration.

This, however, should not lead to shying away from recursion at any price. There are many good applications of recursion, as the following paragraphs and chapters will demonstrate. The fact that implementions of recursive procedures on essentially non-recursive machines exist proves that for practical purposes every recursive program can be transformed into a purely iterative one. This, however, involves the explicit handling of a recursion stack, and these operations will often obscure the essence of a program to such an extent that it becomes most difficult to comprehend. The lesson is that algorithms which by their nature are recursive rather than iterative should be formulated as recursive procedures. In order to appreciate this point, the reader is referred to Programs 2.10 and 2.11 for a comparison.

The remaining part of this chapter is devoted to the development of some recursive programs in situations in which recursion is justifiably appropriate. Also Chaps. 4 and 5 make great use of recursion in cases in which the underlying data structures let the choice of recursive solutions appear obvious and natural.