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).[2] Recursion is an important topic discussed at length in upperlevel computer science courses. This section and the next present simple examples of recursion. This book contains an extensive treatment of recursion. Figure 6.33 (at the end of Section 6.21) summarizes the recursion examples and exercises in the book.
[2] Although many compilers allow function main to call itself, Section 3.6.1, paragraph 3, of the C++ standard document indicates that main should not be called within a program. Its sole purpose is to be the starting point for program execution.
We first consider recursion conceptually, then examine two programs containing recursive functions. Recursive problemsolving 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 socalled 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 piecesa 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 problemthis 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 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.28. Figure 6.28(a) shows how the succession of recursive calls proceeds until 1! is evaluated to be 1, which terminates the recursion. Figure 6.28(b) shows the values returned from each recursive call to its caller until the final value is calculated and returned.
Figure 6.28. Recursive evaluation of 5!.
The program of Fig. 6.29 uses recursion to calculate and print the factorials of the integers 010. (The choice of the data type unsigned long is explained momentarily.) The recursive function factorial (lines 2329) first determines whether the terminating condition number <= 1 (line 25) is true. If number is indeed less than or equal to 1, function factorial 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 ).
Figure 6.29. Demonstrating function factorial.
(This item is displayed on page 291 in the print version)
1 // Fig. 6.29: fig06_29.cpp 2 // Testing the recursive factorial function. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include 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

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 document requires that a variable of type unsigned long int be stored in at least four bytes (32 bits); thus, it 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.29, 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 twobyte) integers. Unfortunately, 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.
The exercises explore using 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 will see when we discuss objectoriented 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,[3] and we work on similar classes of our own in Exercise 9.14 and Exercise 11.5.
[3] Such classes can be found at shoup.net/ntl, cliodhna.cop.uop.edu/~hetrick/csources.html and www.trumphurst.com/cpplibs/datapage.phtml?category='intro'.
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. 
Introduction to Computers, the Internet and World Wide Web
Introduction to C++ Programming
Introduction to Classes and Objects
Control Statements: Part 1
Control Statements: Part 2
Functions and an Introduction to Recursion
Arrays and Vectors
Pointers and PointerBased Strings
Classes: A Deeper Look, Part 1
Classes: A Deeper Look, Part 2
Operator Overloading; String and Array Objects
ObjectOriented Programming: Inheritance
ObjectOriented Programming: Polymorphism
Templates
Stream Input/Output
Exception Handling
File Processing
Class string and String Stream Processing
Web Programming
Searching and Sorting
Data Structures
Bits, Characters, CStrings and structs
Standard Template Library (STL)
Other Topics
Appendix A. Operator Precedence and Associativity Chart
Appendix B. ASCII Character Set
Appendix C. Fundamental Types
Appendix D. Number Systems
Appendix E. C Legacy Code Topics
Appendix F. Preprocessor
Appendix G. ATM Case Study Code
Appendix H. UML 2: Additional Diagram Types
Appendix I. C++ Internet and Web Resources
Appendix J. Introduction to XHTML
Appendix K. XHTML Special Characters
Appendix L. Using the Visual Studio .NET Debugger
Appendix M. Using the GNU C++ Debugger
Bibliography