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.28 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.28 shows the execution of the program, which displays the Fibonacci values for several numbers.
1 // Fig. 6.28: fig06_28.cpp
2 // Recursive function fibonacci.
3 #include <iostream>
4 using namespace std;
5
6 unsigned long fibonacci( unsigned long ); // function prototype
7
8 int main()
9 {
10 // calculate the fibonacci values of 0 through 10
11 for ( unsigned int counter = 0; counter <= 10; ++counter )
12 cout << "fibonacci( " << counter << " ) = "
13 << fibonacci( counter ) << endl;
14
15 // display higher fibonacci values
16 cout << "
fibonacci( 20 ) = " << fibonacci( 20 ) << endl;
17 cout << "fibonacci( 30 ) = " << fibonacci( 30 ) << endl;
18 cout << "fibonacci( 35 ) = " << fibonacci( 35 ) << endl;
19 } // end main
20
21 // recursive function fibonacci
22 unsigned long fibonacci( unsigned long number )
23 {
24 if ( ( 0 == number ) || ( 1 == number ) ) // base cases
25 return number;
26 else // recursion step
27 return fibonacci( number - 1 ) + fibonacci( number - 2 );
28 } // end function fibonacci
fibonacci( 0 ) = 0
fibonacci( 1 ) = 1
fibonacci( 2 ) = 1
fibonacci( 3 ) = 2
fibonacci( 4 ) = 3
fibonacci( 5 ) = 5
fibonacci( 6 ) = 8
fibonacci( 7 ) = 13
fibonacci( 8 ) = 21
fibonacci( 9 ) = 34
fibonacci( 10 ) = 55
fibonacci( 20 ) = 6765
fibonacci( 30 ) = 832040
fibonacci( 35 ) = 9227465
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 16–18). The calls to fibonacci
(lines 13 and 16–18) from main
are not recursive calls, but the calls from line 27 of fibonacci
are recursive. Each time the program invokes fibonacci
(lines 22–28), the function immediately tests the base case to determine whether number
is equal to 0
or 1
(line 24). If this is true, line 25 returns number
. Interestingly, if number
is greater than 1, the recursion step (line 27) generates two recursive calls, each for a slightly smaller problem than the original call to fibonacci
.