14.1 Recursive Functions For Tasks

I remembered too that night which is at the middle of the Thousand and One Nights when Scheherazade (through a magical oversight of the copyist) begins to relate word for word the story of the Thousand and One Nights, establishing the risk of coming once again to the night when she must repeat it, and thus to infinity.

JORGE LUIS BORGES, The Garden of Forking Paths

When you are writing a function to solve a task, one basic design technique is to break the task into subtasks. Sometimes it turns out that at least one of the subtasks is a smaller example of the same task. For example, if the task is to search an array for a particular value, you might divide this into the subtask of searching the first half of the array and the subtask of searching the second half of the array. The subtasks of searching the halves of the array are “smaller” versions of the original task. Whenever one subtask is a smaller version of the original task to be accomplished, you can solve the original task using a recursive function. It takes a little training to easily decompose problems this way, but once you learn the technique, it can be one of the quickest ways to design an algorithm, and, ultimately, a C++ function. We begin with a simple case study to illustrate this technique.

Recursion

In C++, a function definition may contain a call to the function being defined. In such cases, the function is said to be recursive.

Case Study Vertical Numbers

In this case study we design a recursive void function that writes numbers to the screen with the digits written vertically, so that, for example, 1984 would be written as

1
9
8
4

Problem Definition

The declaration and header comment for our function is as follows:

void writeVertical(int n);
//Precondition: n >= 0.
//Postcondition: The number n is written to the screen
//vertically with each digit on a separate line.

Algorithm Design

One case is very simple. If n, the number to be written out, is only one digit long, then just write out the number. As simple as it is, this case is still important, so let’s keep track of it.

Simple Case: If n < 10, then write the number n to the screen.

Now let’s consider the more typical case in which the number to be written out consists of more than one digit. Suppose you want to write the number 1234 vertically so that the result is

1
2
3
4

One way to decompose this task into two subtasks is the following:

1. Output all the digits except the last digit like so:

   1
   2
   3

2. Output the last digit, which in this example is 4.

Subtask 1 is a smaller version of the original task, so we can implement this subtask with a recursive call. Subtask 2 is just the simple case we listed earlier. Thus, an outline of our algorithm for the function writeVertical with parameter n is given by the following pseudocode:

In order to convert this pseudocode into the code for a C++ function, all we need to do is translate the following two pieces of pseudocode into C++ expressions:

• the number n with the last digit removed

and

• the last digit of n

These expressions can easily be translated into C++ expressions using the integer division operators / and % as follows:

n / 10 //the number n with the last digit removed
n % 10 //the last digit of n

For example, 1234 / 10 evaluates to 123, and 1234 % 10 evaluates to 4.

Several factors influenced our selection of the two subtasks we used in this algorithm. One was that we could easily compute the argument for the recursive call to writeVertical (shown in color) that we used in the pseudocode. The number n with the last digit removed is easily computed as n/10. As an alternative, you might have been tempted to divide the subtasks as follows:

1. Output the first digit of n.

2. Output the number n with the first digit removed.

This is a perfectly valid decomposition of the task into subtasks, and it can be implemented recursively. However, it is difficult to calculate the result of removing the first digit from a number, while it is easy to calculate the result of removing the last digit from a number.

Another reason for choosing these sorts of decompositions is that one of the subcases does not involve a recursive call. A successful definition of a recursive function always includes at least one case that does not involve a recursive call (as well as one or more cases that do involve at least one recursive call). This aspect of the recursive algorithm is discussed in the subsections that follow this case study.

Coding

We can now put all the pieces together to produce the recursive function writeVertical shown in Display 14.1. In the next subsection we will explain more details of how recursion works in this example.

Display 14.1 A Recursive Output Function

 1    //Program to demonstrate the recursive function writeVertical.
 2    #include <iostream>
 3    using namespace std;
 4      
 5    void writeVertical(int n);
 6    //Precondition: n >= 0.
 7    //Postcondition: The number n is written to the screen vertically
 8    //with each digit on a separate line.  9     
10    int main( )
11    {
12        cout << "writeVertical(3):" << endl;
13        writeVertical(3);
14     
15        cout<< "writeVertical(12):" <<endl;
16        writeVertical(12);
17     
18        cout<< "writeVertical(123):" <<endl;
19        writeVertical(123);
20     
21        return 0;
22    }
23     
24    //uses iostream:
25    void writeVertical(int n)
26    {
27        if (n < 10)
28        {
29            cout << n << endl;
30        }
31        else //n is two or more digits long:
32        {
33            writeVertical(n / 10);
34            cout << (n % 10) << endl;
35        }
36    }

Sample Dialogue

writeVertical(3):
3
writeVertical(12):
1
2
writeVertical(123):
1
2
3

Tracing a Recursive Call

Let’s see exactly what happens when the following function call is made:

writeVertical(123);

When this function call is executed, the computer proceeds just as it would with any function call. The argument 123 is substituted for the parameter n in the function definition, and the body of the function is executed. After the substitution of 123 for n, the code to be executed is as follows:

Since 123 is not less than 10, the logical expression in the if-else statement is false, so the else part is executed. However, the else part begins with the following function call:

writeVertical(n / 10);

which (since n is equal to 123) is the call

writeVertical(123 / 10);

which is equivalent to

writeVertical(12);

When execution reaches this recursive call, the current function computation is placed in suspended animation and this recursive call is executed. When this recursive call is finished, the execution of the suspended computation will return to this point, and the suspended computation will continue from this point.

The recursive call

writeVertical(12);

is handled just like any other function call. The argument 12 is substituted for the parameter n and the body of the function is executed. After substituting 12 for n, there are two computations, one suspended and one active, as follows:

14.1-3 Full Alternative Text

Since 12 is not less than 10, the Boolean expression in the if-else statement is false and so the else part is executed. However, as you already saw, the else part begins with a recursive call. The argument for the recursive call is n / 10, which in this case is equivalent to 12 / 10. So this second computation of the function writeVertical is suspended and the following recursive call is executed:

writeVertical(12/ 10);

which is equivalent to

writeVertical(1);

At this point there are two suspended computations waiting to resume and the computer begins to execute this new recursive call, which is handled just like all the previous recursive calls. The argument 1 is substituted for the parameter n, and the body of the function is executed. At this point, the computation looks like the following:

14.1-4 Full Alternative Text

Output the digit 1

When the body of the function is executed this time, something different happens. Since 1 is less than 10, the Boolean expression in the if-else statement is true, so the statement before the else is executed. That statement is simply a cout statement that writes the argument 1 to the screen, and so the call writeVertical(1) writes 1 to the screen and ends without any recursive call.

When the call writeVertical(1) ends, the suspended computation that is waiting for it to end resumes where that suspended computation left off, as shown by the following:

14.1-5 Full Alternative Text

Output the digit 2

When this suspended computation resumes, it executes a cout statement that outputs the value 12 % 10, which is 2. That ends that computation, but there is yet another suspended computation waiting to resume. When this last suspended computation resumes, the situation is as follows:

14.1-6 Full Alternative Text

Output the digit 3

When this last suspended computation resumes, it outputs the value 123 % 10, which is 3, and the execution of the original function call ends. And, sure enough, the digits 1, 2, and 3 have been written to the screen one per line, in that order.

A Closer Look at Recursion

The definition of the function writeVertical uses recursion. Yet we did nothing new or different in evaluating the function call writevertical(123). We treated it just like any of the function calls we saw in previous chapters. We just substituted the argument 123 for the parameter n and then executed the code in the body of the function definition. When we reached the recursive call

writeVertical(123 / 10);

we simply repeated this process one more time.

How recursion works

The computer keeps track of recursive calls in the following way. When a function is called, the computer plugs in the arguments for the parameter(s) and begins to execute the code. If it should encounter a recursive call, then it temporarily stops its computation. This is because it must know the result of the recursive call before it can proceed. It saves all the information it needs to continue the computation later on and proceeds to evaluate the recursive call. When the recursive call is completed, the computer returns to finish the outer computation.

How recursion ends

The C++ language places no restrictions on how recursive calls are used in function definitions. However, in order for a recursive function definition to be useful, it must be designed so that any call of the function must ultimately terminate with some piece of code that does not depend on recursion. The function may call itself, and that recursive call may call the function again. The process may be repeated any number of times. However, the process will not terminate unless eventually one of the recursive calls does not depend on recursion. The general outline of a successful recursive function definition is as follows:

• One or more cases in which the function accomplishes its task by using recursive calls to accomplish one or more smaller versions of the task.

• One or more cases in which the function accomplishes its task without the use of any recursive calls. These cases without any recursive calls are called base cases or stopping cases.

Often, an if-else statement determines which of the cases will be executed. A typical scenario is for the original function call to execute a case that includes a recursive call. That recursive call may in turn execute a case that requires another recursive call. For some number of times each recursive call produces another recursive call, but eventually one of the stopping cases should apply. Every call of the function must eventually lead to a stopping case, or else the function call will never end because of an infinite chain of recursive calls. (In practice, a call that includes an infinite chain of recursive calls will usually terminate abnormally rather than actually running forever.)

The most common way to ensure that a stopping case is eventually reached is to write the function so that some (positive) numeric quantity is decreased on each recursive call and to provide a stopping case for some “small” value. This is how we designed the function writeVertical in Display 14.1. When the function writeVertical is called, that call produces a recursive call with a smaller argument. This continues with each recursive call producing another recursive call until the argument is less than 10. When the argument is less than 10, the function call ends without producing any more recursive calls and the process works its way back to the original call and then ends.

General Form of a Recursive Function Definition

The general outline of a successful recursive function definition is as follows:

• One or more cases that include one or more recursive calls to the function being defined. These recursive calls should solve “smaller” versions of the task performed by the function being defined.

• One or more cases that include no recursive calls. These cases without any recursive calls are called base cases or stopping cases.

Pitfall Infinite Recursion

In the example of the function writeVertical discussed in the previous subsections, the series of recursive calls eventually reached a call of the function that did not involve recursion (that is, a stopping case was reached). If, on the other hand, every recursive call produces another recursive call, then a call to the function will, in theory, run forever. This is called infinite recursion. In practice, such a function will typically run until the computer runs out of resources and the program terminates abnormally. Phrased another way, a recursive definition should not be “recursive all the way down.” Otherwise, like the lady’s explanation of the universe given at the start of this chapter, a call to the function will never end, except perhaps in frustration.

Examples of infinite recursion are not hard to come by. The following is a syntactically correct C++ function definition, which might result from an attempt to define an alternative version of the function writeVertical:

void newWriteVertical(int n)
{
    newWriteVertical(n / 10);
    cout << (n % 10) << endl;
}

If you embed this definition in a program that calls this function, the compiler will translate the function definition to machine code and you can execute the machine code. Moreover, the definition even has a certain reasonableness to it. It says that to output the argument to newWriteVertical, first output all but the last digit and then output the last digit. However, when called, this function will produce an infinite sequence of recursive calls. If you call newWriteVertical(12), that execution will stop to execute the recursive call newWriteVertical (12/10), which is equivalent to newWriteVertical(1). The execution of that recursive call will, in turn, stop to execute the recursive call

newWriteVertical(1/10);

which is equivalent to

newWriteVertical(0);

That, in turn, will stop to execute the recursive call newWriteVertical (0/10); which is also equivalent to

newWriteVertical(0);

and that will produce another recursive call to again execute the same recursive function call newWriteVertical(0); and so on, forever. Since the definition of newWriteVertical has no stopping case, the process will proceed forever (or until the computer runs out of resources).

Self-Test Exercises

1. What is the output of the following program?

   #include <iostream>
   using namespace std;
   void cheers(int n);
   int main()
   {
       cheers(3);
       return 0;
   }
   void cheers(int n)
   {
   if (n == 1)
   {
           cout << "Hurray\n";
   }
   else
   {
           cout << "Hip ";
           cheers(n − 1);
       }
   }

2. Write a recursive void function that has one parameter which is a positive integer and that writes out that number of asterisks '*' to the screen all on one line.

3. Write a recursive void function that has one parameter, which is a positive integer. When called, the function writes its argument to the screen backward. That is, if the argument is 1234, it outputs the following to the screen:

   4321

4. Write a recursive void function that takes a single int argument n and writes the integers 1, 2, ..., n.

5. Write a recursive void function that takes a single int argument n and writes integers n, n–1, ..., 3, 2, 1. (Hint: Notice that you can get from the code for Self-Test Exercise 4 to that for Self-Test Exercise 5, or vice versa, by an exchange of as little as two lines.)

Stacks for Recursion

In order to keep track of recursion, and a number of other things, most computer systems make use of a structure called a stack. A stack is a very specialized kind of memory structure that is analogous to a stack of paper. In this analogy there is an inexhaustible supply of extra blank sheets of paper. To place some information in the stack, it is written on one of these sheets of paper and placed on top of the stack of papers. To place more information in the stack, a clean sheet of paper is taken, the information is written on it, and this new sheet of paper is placed on top of the stack. In this straightforward way, more and more information may be placed on the stack.

Getting information out of the stack is also accomplished by a very simple procedure. The top sheet of paper can be read, and when it is no longer needed, it is thrown away. There is one complication: Only the top sheet of paper is accessible. In order to read, say, the third sheet from the top, the top two sheets must be thrown away. Since the last sheet that is put on the stack is the first sheet taken off the stack, a stack is often called a last-in/first-out (LIFO) memory structure.

Using a stack, the computer can easily keep track of recursion. Whenever a function is called, a new sheet of paper is taken. The function definition is copied onto this sheet of paper, and the arguments are plugged in for the function parameters. Then the computer starts to execute the body of the function definition. When it encounters a recursive call, it stops the computation it is doing on that sheet in order to compute the recursive call. But before computing the recursive call, it saves enough information so that, when it does finally complete the recursive call, it can continue the stopped computation. This saved information is written on a sheet of paper and placed on the stack. A new sheet of paper is used for the recursive call. The computer writes a second copy of the function definition on this new sheet of paper, plugs in the arguments for the function parameters, and starts to execute the recursive call. When it gets to a recursive call within the recursively called copy, it repeats the process of saving information on the stack and using a new sheet of paper for the new recursive call. This process is illustrated in the earlier subsection entitled “Tracing a Recursive Call.” Even though we did not call it a stack in that section, the illustrations of computations placed one on top of the other demonstrate the actions of the stack.

Recursion and the Stack

This process continues until some recursive call to the function completes its computation without producing any more recursive calls. When that happens, the computer turns its attention to the top sheet of paper on the stack. This sheet contains the partially completed computation that is waiting for the recursive computation that just ended. So, it is possible to proceed with that suspended computation. When that suspended computation ends, the computer discards that sheet of paper, and the suspended computation that is below it on the stack becomes the computation on top of the stack. The computer turns its attention to the suspended computation that is now on the top of the stack, and so forth. The process continues until the computation on the bottom sheet is completed. Depending on how many recursive calls are made and how the function definition is written, the stack may grow and shrink in any fashion. Notice that the sheets in the stack can only be accessed in a last-in/first-out fashion, but that is exactly what is needed to keep track of recursive calls. Each suspended version is waiting for the completion of the version directly above it on the stack.

Needless to say, computers do not have stacks of paper of this kind. This is just an analogy. The computer uses portions of memory rather than pieces of paper. The contents of one of these portions of memory (“sheets of paper”) is called an activation frame. These activation frames are handled in the last-in/first-out manner we just discussed. (The activation frames do not contain a complete copy of the function definition, but merely reference a single copy of the function definition. However, an activation frame contains enough information to allow the computer to act as if the frame contained a complete copy of the function definition.)

Stack

A stack is a last-in/first-out memory structure. The first item referenced or removed from a stack is always the last item entered into the stack. Stacks are used by computers to keep track of recursion (and for other purposes).

Pitfall Stack Overflow

There is always some limit to the size of the stack. If there is a long chain in which a function makes a recursive call to itself, and that call results in another recursive call, and that call produces yet another recursive call, and so forth, then each recursive call in this chain will cause another activation frame to be placed on the stack. If this chain is too long, then the stack will attempt to grow beyond its limit. This is an error condition known as a stack overflow. If you receive an error message that says stack overflow, it is likely that some function call has produced an excessively long chain of recursive calls. One common cause of stack overflow is infinite recursion. If a function is recursing infinitely, then it will eventually try to make the stack exceed any stack size limit.

Recursion Versus Iteration

Recursion is not absolutely necessary. In fact, some programming languages do not allow it. Any task that can be accomplished using recursion can also be done in some other way without using recursion. For example, Display 14.2 contains a nonrecursive version of the function given in Display 14.1. The nonrecursive version of a function typically uses a loop (or loops) of some sort in place of recursion. For that reason, the nonrecursive version is usually referred to as an iterative version. If the definition of the function writeVertical given in Display 14.1 is replaced by the version given in Display 14.2, then the output will be the same. As is true in this case, a recursive version of a function can sometimes be much simpler than an iterative version.

Display 14.2 Iterative Version of the Function in Display 14.1

 1    //Uses iostream:
 2    void writeVertical(int n)
 3    {
 4        int tensInN = 1;
 5        int leftEndPiece = n;
 6        while (leftEndPiece> 9)
 7        {
 8            leftEndPiece = leftEndPiece/10;
 9            tensInN = tensInN * 10;
10        }
11        //tensInN is a power of ten that has the same number
12        //of digits as n. For example, if n is 2345, then
13        //tensInN is 1000.
14     
15        for (int powerOf10 = tensInN;
16            powerOf10 > 0; powerOf10 = powerOf10/10)
17        {
18            cout << (n/powerOf10) <<endl;
19            n = n % powerOf10;
20        }
21    }

A recursively written function will usually run slower and use more storage than an equivalent iterative version. Although the iterative version of writeVertical given in Display 14.2 looks like it uses more storage and does more computing than the recursive version in Display 14.1, the two versions of writeVertical actually use comparable storage and do comparable amounts of computing. In fact, the recursive version may use more storage and run somewhat slower, because the computer must do a good deal of work manipulating the stack in order to keep track of the recursion. However, since the system does all this for you automatically, using recursion can sometimes make your job as a programmer easier and can sometimes produce code that is easier to understand. As you will see in the examples in this chapter and in the Self-Test Exercises and Programming Projects, sometimes a recursive definition is simpler and clearer; other times, an iterative definition is simpler and clearer.

Self-Test Exercises

6. If your program produces an error message that says stack overflow, what is a likely source of the error?

7. Write an iterative version of the function cheers defined in Self-Test Exercise 1.

8. Write an iterative version of the function defined in Self-Test Exercise 2.

9. Write an iterative version of the function defined in Self-Test Exercise 3.

10. Trace the recursive solution you made to Self-Test Exercise 4.

11. Trace the recursive solution you made to Self-Test Exercise 5.