The Fibonacci series
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.
The series occurs in nature and, in particular, describes a form of spiral. The ratio of successive Fibonacci numbers converges on a constant value of 1.618.... This number, too, frequently occurs in nature and has been called the golden ratio or the golden mean. Humans tend to find the golden mean aesthetically pleasing. Architects often design windows, rooms and buildings whose length and width are in the ratio of the golden mean. Postcards are often designed with a golden mean length/width ratio.
The Fibonacci series can be defined recursively as follows:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n 1) + fibonacci(n 2)
The program of Fig. 6.30 calculates the nth Fibonacci number recursively by using function fibonacci. Notice that Fibonacci numbers also tend to become large quickly, although slower than factorials do. Therefore, we chose the data type unsigned long for the parameter type and the return type in function fibonacci. Figure 6.30 shows the execution of the program, which displays the Fibonacci values for several numbers.
Figure 6.30. Demonstrating function fibonacci.
(This item is displayed on page 293 in the print version)
1 // Fig. 6.30: fig06_30.cpp 2 // Testing the recursive fibonacci function. 3 #include 4 using std::cout; 5 using std::cin; 6 using std::endl; 7 8 unsigned long fibonacci( unsigned long ); // function prototype 9 10 int main() 11 { 12 // calculate the fibonacci values of 0 through 10 13 for ( int counter = 0; counter <= 10; counter++ ) 14 cout << "fibonacci( " << counter << " ) = " 15 << fibonacci( counter ) << endl; 16 17 // display higher fibonacci values 18 cout << "fibonacci( 20 ) = " << fibonacci( 20 ) << endl; 19 cout << "fibonacci( 30 ) = " << fibonacci( 30 ) << endl; 20 cout << "fibonacci( 35 ) = " << fibonacci( 35 ) << endl; 21 return 0; // indicates successful termination 22 } // end main 23 24 // recursive method fibonacci 25 unsigned long fibonacci( unsigned long number ) 26 { 27 if ( ( number == 0 )  ( number == 1 ) ) // base cases 28 return number; 29 else // recursion step 30 return fibonacci( number  1 ) + fibonacci( number  2 ); 31 } // end function fibonacci

The application begins with a for statement that calculates and displays the Fibonacci values for the integers 010 and is followed by three calls to calculate the Fibonacci values of the integers 20, 30 and 35 (lines 1820). The calls to fibonacci (lines 15, 18, 19 and 20) from main are not recursive calls, but the calls from line 30 of fibonacci are recursive. Each time the program invokes fibonacci (lines 2531), the function immediately tests the base case to determine whether number is equal to 0 or 1 (line 27). If this is true, line 28 returns number. Interestingly, if number is greater than 1, the recursion step (line 30) generates two recursive calls, each for a slightly smaller problem than the original call to fibonacci. Figure 6.31 shows how function fibonacci would evaluate fibonacci( 3 ).
Figure 6.31. Set of recursive calls to function fibonacci.
(This item is displayed on page 294 in the print version)
This figure raises some interesting issues about the order in which C++ compilers will evaluate the operands of operators. This is a separate issue from the order in which operators are applied to their operands, namely, the order dictated by the rules of operator precedence and associativity. Figure 6.31 shows that evaluating fibonacci( 3 ) causes two recursive calls, namely, fibonacci( 2 ) and fibonacci( 1 ). But in what order are these calls made?
Most programmers simply assume that the operands are evaluated left to right. The C++ language does not specify the order in which the operands of most operators (including +) are to be evaluated. Therefore, the programmer must make no assumption about the order in which these calls execute. The calls could in fact execute fibonacci( 2 ) first, then fibonacci( 1 ), or they could execute in the reverse order: fibonacci( 1 ), then fibonacci( 2 ). In this program and in most others, it turns out that the final result would be the same. However, in some programs the evaluation of an operand can have side effects (changes to data values) that could affect the final result of the expression.
The C++ language specifies the order of evaluation of the operands of only four operatorsnamely, &&, , the comma (,) operator and ?:. The first three are binary operators whose two operands are guaranteed to be evaluated left to right. The last operator is C++'s only ternary operator. Its leftmost operand is always evaluated first; if it evaluates to nonzero (true), the middle operand evaluates next and the last operand is ignored; if the leftmost operand evaluates to zero (false), the third operand evaluates next and the middle operand is ignored.
Common Programming Error 6.25
Writing programs that depend on the order of evaluation of the operands of operators other than &&, , ?: and the comma (,) operator can lead to logic errors. 
Portability Tip 6.3
Programs that depend on the order of evaluation of the operands of operators other than &&, , ?: and the comma (,) operator can function differently on systems with different compilers. 
A word of caution is in order about recursive programs like the one we use here to generate Fibonacci numbers. Each level of recursion in function fibonacci has a doubling effect on the number of function calls; i.e., the number of recursive calls that are required to calculate the nth Fibonacci number is on the order of 2n. This rapidly gets out of hand. Calculating only the 20th Fibonacci number would require on the order of 220 or about a million calls, calculating the 30th Fibonacci number would require on the order of 230 or about a billion calls, and so on. Computer scientists refer to this as exponential complexity. Problems of this nature humble even the world's most powerful computers! Complexity issues in general, and exponential complexity in particular, are discussed in detail in the upperlevel computer science course generally called "Algorithms."
Performance Tip 6.8
Avoid Fibonaccistyle recursive programs that result in an exponential "explosion" of calls. 
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