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.26 calculates the nth Fibonacci number recursively by using function fibonacci. Fibonacci numbers 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.26 shows the execution of the program, which displays the Fibonacci values for several numbers.

The application begins with a for statement that calculates and displays the Fibonacci values for the integers 0–10 and is followed by three calls to calculate the Fibonacci values of the integers 20, 30 and 35 (lines 15–17). The calls to fibonacci in main (lines 12 and 15–17) are not recursive calls, but the calls from line 26 of fibonacci are recursive. Each time the program invokes fibonacci (lines 21–28), the function immediately tests the base case to determine whether number is equal to 0 or 1 (line 22). If this is true, line 23 returns number. Interestingly, if number is greater than 1, the recursion step (line 26) generates two recursive calls, each for a slightly smaller problem than the original call to fibonacci.

Figure 6.27 shows how function fibonacci would evaluate fibonacci(3). This figure raises some interesting issues about the order in which C++ compilers 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.27 shows that evaluating fibonacci(3) causes two recursive calls, namely, fibonacci(2) and fibonacci(1). In what order are these calls made?

Most programmers simply assume that the operands are evaluated left to right. C++ does not specify the order in which the operands of most operators (including +) are to be evaluated. Therefore, you 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.

C++ specifies the order of evaluation of the operands of only four operators—&&, ||, comma (,) 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 true, the middle operand evaluates next and the last operand is ignored; if the leftmost operand evaluates to false, the third operand evaluates next and the middle operand is ignored.

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 $2^n$. This rapidly gets out of hand. Calculating only the 20th Fibonacci number would require on the order of $2^{20}$ or about a million calls, calculating the 30th Fibonacci number would require on the order of $2^{30}$ or about a billion calls, and so on. Computer scientists refer to this as exponential complexity. Problems of this nature can humble even the world’s most powerful computers as n becomes large! Complexity issues in general, and exponential complexity in particular, are discussed in detail in the upper-level computer science course typically called Algorithms.