6.19. Recursion
The programs we have discussed are
generally structured as functions that call one another in a disciplined,
hierarchical manner. For some problems, it is useful to have functions call themselves. A recursive function is a
function that calls itself, either directly, or indirectly (through another
function). [Note:
Although many compilers allow function main to
call itself, Section 3.6.1, paragraph 3, and Section 5.2.2, paragraph 9, of the
C++ standard document indicate that main
should not be called within a program or recursively. Its sole purpose is to be
the starting point for program execution.]This section and the next present
simple examples of recursion.
We first consider recursion
conceptually, then examine two programs containing recursive functions.
Recursive problem-solving approaches have a number of elements in common. A
recursive function is called to solve a problem. The function actually knows how
to solve only the simplest case(s), or so-called base case(s). If the
function is called with a base case, the function simply returns a result. If
the function is called with a more complex problem, it typically divides the
problem into two conceptual pieces—a piece that the function knows how to do and
a piece that it does not know how to do. To make recursion feasible, the latter
piece must resemble the original problem, but be a slightly simpler or slightly
smaller version. This new problem looks like the original problem, so the
function launches (calls) a fresh copy of itself to work on the smaller
problem—this is referred to as a recursive
call and is also called the recursion step. The recursion step often includes
the keyword return, because its result will
be combined with the portion of the problem the function knew how to solve to
form a result that will be passed back to the original caller, possibly
main.
The recursion step executes while
the original call to the function is still "open," i.e., it has not yet finished
executing. The recursion step can result in many more such recursive calls, as
the function keeps dividing each new subproblem with which the function is
called into two conceptual pieces. In order for the recursion to eventually
terminate, each time the function calls itself with a slightly simpler version
of the original problem, this sequence of smaller and smaller problems must
eventually converge on the base case. At that point, the function recognizes the
base case and returns a result to the previous copy of the function, and a
sequence of returns ensues all the way up the line until the original function
call eventually returns the final result to main. All of this sounds quite exotic compared to the kind
of "conventional" problem solving we have been using to this point. As an
example of these concepts at work, let us write a recursive program to perform a
popular mathematical calculation.
The factorial of a nonnegative
integer n, written n! (and pronounced "n
factorial"), is the product
n · (n – 1) · (n – 2) · ... ·
1
with 1! equal to 1, and 0! defined to be 1.
For example, 5! is the product 5 · 4 · 3 · 2 · 1, which is equal to 120.
The factorial of an integer,
number, greater than or equal to 0, can be calculated iteratively (nonrecursively) by using a
for statement as follows:
factorial = 1;
for ( int counter = number; counter >= 1; counter-- )
factorial *= counter;
A recursive definition of the
factorial function is arrived at by observing the following algebraic
relationship:
n! = n · (n
– 1)!
For example, 5! is clearly equal to 5 *
4! as is shown by the following:
5! = 5 · 4 · 3 · 2 · 1
5! = 5 · (4 · 3 · 2 · 1)
5! = 5 · (4!)
The evaluation of 5! would proceed as
shown in Fig. 6.27.
Figure 6.27(a) shows how the succession of recursive calls proceeds
until 1! is evaluated to be 1, which terminates the recursion. Figure 6.27(b) shows the values returned from each recursive call to
its caller until the final value is calculated and returned.
The program of Fig. 6.28
uses recursion to calculate and print the factorials of the integers 0–10. (The
choice of the data type unsigned long
is explained momentarily.) The recursive function factorial (lines 23–29) first determines whether the terminating
condition number <= 1 (line 25) is true. If number is less than or equal to 1, the factorial function returns 1 (line 26), no further recursion is necessary and
the function terminates. If number is greater than
1, line 28 expresses the problem as the product of number and a recursive call to factorial evaluating the factorial
of number - 1. Note that factorial( number-1) is a slightly
simpler problem than the original calculation factorial( number
).
Fig. 6.28. Demonstrating the recursive function
factorial.
1 // Fig. 6.28: fig06_28.cpp
2 // Demonstrating the recursive function factorial.
3 #include <iostream>
4 using std::cout;
5 using std::endl;
6
7 #include <iomanip>
8 using std::setw;
9
10 unsigned long factorial( unsigned long ); // function prototype
11
12 int main()
13 {
14 // calculate the factorials of 0 through 10
15 for ( int counter = 0; counter <= 10; counter++ )
16 cout << setw( 2 ) << counter << "! = " << factorial( counter )
17 << endl;
18
19 return 0; // indicates successful termination
20 } // end main
21
22 // recursive definition of function factorial
23 unsigned long factorial( unsigned long number )
24 {
25 if ( number <= 1 ) // test for base case
26 return 1; // base cases: 0! = 1 and 1! = 1
27 else // recursion step
28 return number * factorial( number - 1 );
29 } // end function factorial
|
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
|
Function factorial has been declared to receive a
parameter of type unsigned long and return a result of type
unsigned long. This is shorthand notation for unsigned long int. The C++ standard requires that a variable of type
unsigned long int be at least as big as an int. Typically, an
unsigned long int is stored in at least four
bytes (32 bits); such a variable can hold a value in the range 0 to at least
4294967295. (The data type long int is also stored in at least four bytes and can hold a value at
least in the range –2147483648 to 2147483647.) As can be seen in Fig. 6.28, factorial values become large quickly. We chose the
data type unsigned long so that the program
can calculate factorials greater than 7! on computers with small (such as
two-byte) integers. Unfortunately, the function factorial produces large values so quickly that even unsigned
long does not help us compute many factorial values
before even the size of an unsigned long variable is exceeded.
We could use
variables of data type double to calculate
factorials of larger numbers. This points to a weakness in most programming
languages, namely, that the languages are not easily extended to handle the
unique requirements of various applications. As we'll see when we discuss
object-oriented programming in more depth, C++ is an extensible language that
allows us to create classes that can represent arbitrarily large integers if we
wish. Such classes already are available in popular class libraries.
Common Programming Error 6.24
|
Either omitting
the base case, or writing the recursion step incorrectly so that it does not
converge on the base case, causes "infinite" recursion, eventually exhausting
memory. This is analogous to the problem of an infinite loop in an iterative
(nonrecursive)
solution. |
No comments:
Post a Comment