Previous Section
 < Free Open Study > 
Next Section


7.13 Removing Recursion

In cases where a recursive solution is not desired, either because the language doesn't support recursion or because the recursive solution is deemed too costly in terms of space or time, you can implement a recursive algorithm as a nonrecursive function. Two general techniques are often substituted for recursion: iteration and stacking.

Iteration

When the recursive call is the last action executed in a recursive function, an interesting situation occurs. The recursive call causes an activation record to be put on the run-time stack to hold the function's parameters and local variables. When this recursive call finishes executing, the run-time stack is popped and the previous values of the variables are restored. But because the recursive call is the last statement in the function, the function terminates without using these values. Thus the pushing and popping of activation records is a superfluous activity. All we really need to do is to change the "smaller-caller" variable(s) on the recursive call's parameter list and then "jump" back to the beginning of the function. In other words, we really need a loop.

For instance, as explained later in this chapter, the function ValueInList is a poor use of recursion. It is a simple matter to remove the recursion from this function. The last statement executed in the general case is the recursive call to itself, so let's replace this recursion with a loop.

The recursive solution has two base cases: (1) we find the value and (2) we reach the end of the list without finding the value. The base cases solve the problem without further executions of the function. In the iterative solution, the base cases become the terminating conditions of the loop:

while (!found && moreToSearch)

When the terminating conditions are met, the problem is solved without further executions of the loop body.

In the general case of the recursive solution, ValueInList is called to search the remaining, unsearched part of the list. Each recursive execution of the function processes a smaller version of the problem. The smaller-caller question is answered affirmatively because startIndex is incremented, shrinking the unsearched part of the list on each recursive call. Similarly, in an iterative solution, each subsequent execution of the loop body processes a smaller version of the problem. The unsearched part of the list shrinks with each execution of the loop body because startIndex is incremented.

Here is the iterative version of the function:

bool ValueInList(ListType list, int value, int startIndex)
{
  bool found = false;

  while (!found && startIndex < list.length)
    if (value == list.info[startIndex])
      found = true;
    else startIndex++;
  return found;
}

Cases where the recursive call is the last statement executed are called tail recursion. Note that the recursive call is not necessarily the last statement in the function. For instance, the recursive call in the following version of ValueInList is still tail recurlion, even though it is not the last statement in the function:

Tail recursion The case in which a function contains only a single recursive invocation and it is the last statement to be executed in the function

bool ValueInList(ListType list, int value, int startIndex)
{
  if (list.info[startIndex] == value)
    return true;
  else if (startIndex != list.length-1)
    return ValueInList(list, value, startIndex+l);
  else return false;
}

The recursive call is the last statement executed in the general case-thus it involves tail recursion. To remove recursion from the solution, tail recursion is usually replaced by iteration. In fact, many compilers catch tail recursion and automatically replace it with iteration.

Stacking

When the recursive call is not the last action executed in a recursive function, we cannot simply substitute a loop for the recursion. For instance, in the function RevPrint we make the recursive call and then print the value in the current node. In such a case, we must replace the stacking performed by the system with stacking performed by the programmer.

How would we write RevPrint nonrecursively? As we traverse the list, we must keep track of the pointer to each node, until we reach the end of the list (when our traversing pointer equals NULL). We then print the info data member of the last node. Next, we back up and print again, back up and print again, and so on, until we have printed the first list element.

We already know of a data structure in which we can store pointers and retrieve them in reverse order: the stack. The general task for RevPrint is as follows:

A nonrecursive RevPrint function may be coded as shown below. Note that we now make RevPrint be a member function of the class ListType instead of a helper function. Because RevPrint no longer has a parameter, we don't have to deal with the problem of having the client pass the (inaccessible) pointer to the beginning of the linked list.

#include "StackType.h"
void ListType::RevPrint()
{
  StackType<NodeType*> stack;
  NodeType* listPtr;

  listPtr = listData:

  while (listPtr != NULL)  // Put pointers onto the stack.
  {
    stack.Push(listPtr);
    listPtr = listPtr->next;
  }
  // Retrieve pointers in reverse order and print elements.
  while (!stack.IsEmpty())
  {
    listPtr = stack.Top();
    stack.Pop();
    std::cout  << listPtr->info;
  )
}

Notice that the nonrecursive version of RevPrint is quite a bit longer than its recursive counterpart, especially if we add in the code for the stack routines Push, Pop, Top, and IsEmpty. This verbosity reflects our need to stack and unstack the pointers explicitly. In the recursive version, we just called RevPrint recursively, and let the runtime stack keep track of the pointers.



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