Previous Section
 < Free Open Study > 
Next Section


7.7 Recursive Linked List Processing

Let's look next at a different kind of problem-a function that prints out the elements in a dynamically allocated linked list. The list has been implemented using the following declarations. For this example, ListType is a class rather than a class template. NodeType is a struct rather than a struct template, and the info member of type NodeType is of type int.

struct NodeType;
class ListType
{
public:
  // Prototypes of member functions
private:
  NodeType* listData;
};

By now you are probably protesting that this task is so simple to accomplish iteratively (while (ptr != NULL)) that it does not make any sense to write it recursively. So let's make the task more fun: Print out the elements in the list in reverse order. This problem is much more easily and "elegantly" solved recursively.

What is the task to be performed? The algorithm follows and is illustrated in Figure 7.3.

Click To expand
Figure 7.3: Recursive RevPrint

The second part of the task is simple. If listPtr points to the first node in the list, we can print out its contents with the statement cout << listPtr->info. The first part of the task-printing out all the other nodes in the list in reverse order-is also simple, because we have a routine that prints out lists in reverse order: We just call the function RevPrint recursively. Of course, we have to adjust the parameter somewhat, to RevPrint (listPtr->next). This call says "Print, in reverse order, the linked list pointed to by listPtr->next." This task, in turn, is accomplished recursively in two steps:

Of course, the first part of this task is accomplished recursively. Where does it all end? We need a base case. We can stop calling RevPrint when we have completed its smallest case: RevPrint-ing a list of one element. Then the value of listPtr->next is NULL, and we can stop making recursive calls. Let's summarize the problem.

The other recursive routines that we have written have been value-returning functions. RevPrint, however, is a void function. Each function call simply performs an action (printing the contents of a list node) without returning a value to the calling code.

void RevPrint(NodeType* listPtr)
{
  if (listPtr != NULL)
  {
    RevPrint(listPtr->next);
    std::cout  << listPtr->info  << std::end1;
  }
}

Given our ListType class, can we make RevPrint become a public member function of the class? The answer is no, and here is the reason: To print the entire linked list, the client's initial call to RevPrint must pass as a parameter the pointer to the first node in the list. In the ListType class, this pointer (listPtr) is a private member of the class, so the following client code is not permitted:

List.RevPrint(list.listData);    // Not allowed; listData is private

Therefore, we must treat RevPrint as an auxiliary, nonmember function and define a member function, say, PrintReversed, that calls RevPrint:

void PrintReversed();      // Prototype in ListType class declaration
  .
  .
  .
void ListType::PrintReversed()
{
  RevPrint(listData);
}

Given this design, the client can print the entire list with the following function call:

list.PrintReversed();

Let's verify RevPrint using the Three-Question Method.

  1. The Base-Case Question: The base case is implied. When listPtr is equal to NULL, we return to the statement following the last recursive call to RevPrint, and no further recursive calls are made. The answer is yes.

  2. The Smaller-Caller Question: The recursive call passes the list pointed to by listPtr->next, which is one node smaller than the list pointed to by listPtr. The answer is yes.

  3. The General-Case Question: We assume that RevPrint (listPtr->next) correctly prints out the rest of the list in reverse order; this call, followed by the statement printing the value of the first element, gives us the whole list, printed in reverse order. The answer is yes.

How would you change the function RevPrint (in addition to changing its name) to make it print out the list in forward rather than reverse order? We leave this modification as an exercise.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)