6.2.2 A Recursive Function

A recursive implementation can also be developed for traverse. Begin with a recursive algorithm for traversing a list-structure; this is obtained directly from the recursive definition of a list-structure traversal.

1. Initialize the current record.

2. While there is a current record,

a. process the current record;

b. if the current record is complex, then

i. traverse the current record's sublist;

c. update the current record to its successor record.

Once more we need the variable ptr to point to the current record, and the variable nextsublist to point to a sublist. Again, the list-structure is treated as a data abstraction. Also, to modularize functionally, assume that a function traverse is available to implement task (i). The algorithm can now be refined:

1. Set ptr to ls

2. While ptr is not null,

a. Process z(ls, ptr);

b. if complex (ptr), then

i. Set nextsublist to sublist (ptr),

traverse (nextsublist);

c. Set ptr to next (ptr).

This refinement is implemented in the following recursive procedure.

Recursive Version

traverse (pls)

/* Accesses and processes each record

of the list-structure ls.

*/

liststructurepointer *pls;

{

liststructurepointer ptr,nextsublist,null,

setnull(),next (),sublist();

null = setnull();

>Comment

ptr = *pls;

>Comment

while(ptr != null)

{

>Comment

process(pls,ptr);

>Comment

if(complex(ptr))

{

>Comment

nextsublist = sublist(ptr);

>Comment

traverse(&nextsublist);

}

>Comment

ptr = next(ptr);

}

}

Notice that this program, at the point when it encounters a complex record and hence must traverse its sublist, does so by simply invoking a module that does that traversal梚tself. After that traversal is complete, it merely resumes where it left off. In contrast, the nonrecursive version must perform its own bookkeeping to keep track of where to resume each time it encounters a complex record and then retrieve that information when it is needed.

A number of comments are in order about the two implementations of traverse. First, imagine that the recursive procedure traverse is presented to you with the statement that it is a refined version of the definition of traversal of a list-structure. It is easy to see that this is so. Contrast this with the effort involved in seeing that the nonrecursive version of traverse is also a refined version of the same defining algorithm. Second, the recursive version is more concise than the nonrecursive. Third, the recursive traverse is almost a direct translation of the defining algorithm. It required very little effort to achieve it in this case, because the definition is itself a recursive description.

These comments usually hold for algorithms that process data structures that can be defined recursively, such as list-structures. This is not an accident but can be expected when we deal with complex data structures. Recursive definitions allow concise descriptions of complex algorithms and data structures. Concise descriptions allow us to deal more easily with their complexity. ln fact, it is difficult to develop a definition for a list-structure traversal that has no vagueness, is applicable to any list-structure, and does not involve recursion. Recursive definitions are especially useful to the programmer dealing with complex data structures, because they lead systematically and directly to recursive programs for their processing.