4.3: A Close Look at the Execution of Recursive Programs

When any program invokes one of its functions, it is because the task performed by that component must now be carried out. Global variables and variables passed by address (pointers) specify storage that is not local to the component but that it may reference and change. It may also reference and change static variables. All such storage represents the data the component is to process. Any changes by the component to the data are reflected back in the data's storage.

Parameters passed to a function by value also specify storage that is not local to it, but these parameters are treated differently. When the component is invoked, their values are copied into storage that is local to the component. It is these local copies that are referenced, and perhaps changed, by the component as it executes, but such changes are not reflected back to the original values. In this way the information passed by value is made accessible to the component, which may even change the local copies, but such changes are kept local; the original nonlocal values are untouched.

In effect, these copies are treated as if they were additional local variables of the component. The actual local variables of the component represent temporary information that the component uses to do its job. Both the local copies and local variables disappear when the task is completed. This storage for local copies and local variables serves as a "scratchpad" for use by the component. The scratchpad contains information used temporarily by the component to perform its task on the data. This view of the data and scratchpad of a component is depicted in Figure 4.7.

The component may, in turn, invoke another component, which may invoke still another, and so on. Each time this is done, the calling component suspends its operation, so all components of the sequence, except the last, are waiting.

When the last component completes its task, the component that invoked it then continues. In order for this to happen, each component must remember from whence it was called. Also, upon return to the correct place, the scratchpad of the calling component must be the same as before the call. For nonrecursive programs, the important point is that each component must retain only one returning point, and the scratchpad of a component is automatically retained when it invokes another component.

With recursive programs the situation is considerably different, as evidenced by Figures 4.2, 4.4, and 4.6. First, when a recursive function is invoked, this may be the initial, first, second, or nth recursive call to it. If it is the nth recursive call, there may be as many as (n + 1) returning places to be retained, not just one. Second, there may be (n + l) scratchpads to be retained. How many there are is determined by the number of calls that are currently suspended.

Figure 4.7 Data and Scratchpad for a Component

Suppose that this number is k, that the return for the initial call is handled separately, and also that the scratchpad for the currently executing call is associated with the function. The number of sets of additional returns and scratchpads that must be retained is then k. The depth of a recursive program is given by the maximum value of k. It is the depth that determines the amount of storage required by the function. The following examples illustrate these ideas.

Example 4.1

In Figure 4.2, when the tenth recursive call (k = 3) is made to towers, there are three returns and three sets of scratchpads to remember in addition to the initial call's return.

[2] and n = 4, i = l, a = 2, f = 3 for the initial call

[1] and n = 3, i = 2, a = 1, f = 3 for the eighth recursive call

[1] and n = 2, i = 2, a = 3, f = 1 for the ninth recursive call

n = 1, i = 2, a = 1, f = 3 for the tenth recursive call are stored, by our assumption, local to towers. In general, the depth of recursion will be n - l. Using our terminology, there are no data. n

Example 4.2

In Figure 4.4, when the third recursive call is made to copy, there are three returns and three sets of scratchpads to be retained beside the initial call's return:

first0, null0, rest0 for the initial call

first1, null1, rest1 for the first recursive call

first2, null2, rest2 for the second recursive call

No returns are shown since they all return to the same place: the statement setlink(*psecond, rest). The depth of the recursion is one less than the length of the list to be copied. The data for the initial call is second, while for the (n + 1)th recursive call it is restn. A change to rest in the (n + 1)th call is reflected in the scratchpad for the nth call. Storage could be saved by making null global to copy. n

Example 4.3

In Figure 4.6 the situation corresponds to a point in the initial call when the second and then the third recursive calls to next are made. The local variable i is not shown, and the three scratchpad values are

n = 4 for the initial call

n = 3 for the second recursive call

n = 2 for the third recursive call

Again, the returns are all the same, to the statement following the recursive call to next, so they are not shown. The depth of the recursion is n - 1. The data consist of p, ptr, pred, and done. n

It should by now be clear that the storage required by a recursive function is proportional to its depth. The execution time, on the other hand, has to do with the total number of recursive calls that are required to complete the initial call. This explains why the recursive solution to Counting Squares (Section 4.2.6) is so inefficient both in time and in storage.