In some cases, recursion enables you to create an intuitive, straightforward, simple Point solution to a problem.
The factorial function in the preceding section easily could be rewritten without using recursion. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve. Consider the well-known Fibonacci series problem, as follows:
The series: 0 1 1 2 3 5 8 13 21 34 55 89 . . .
Indices: 0 1 2 3 4 5 6 7 8 9 10 11
The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series. The series can be defined recursively as follows:
fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index – 2) + fib(index – 1); index >= 2
The Fibonacci series was named for Leonardo Fibonacci, a medieval mathematician, who originated it to model the growth of the rabbit population. It can be applied in numeric optimization and in various other areas.
How do you find fib(index) for a given index? It is easy to find fib(2) because you know fib(0) and fib(1). Assuming that you know fib(index – 2) and fib(index – 1), fib(index) can be obtained immediately. Thus, the problem of computing fib(index) is reduced to computing fib(index – 2) and fib(index – 1). When computing fib(index – 2) and fib(index – 1), you apply the idea recursively until index is reduced to 0 or 1.
The base case is i ndex = 0 or i ndex = 1. If you call the function with i ndex = 0 or index = 1, it immediately returns the result. If you call the function with index >= 2, it divides the problem into two subproblems for computing fib(index – 1) and fib(index – 2) using recursive calls. The recursive algorithm for computing fib(index) can be simply described as follows:
if (index == 0)
return 0;
else if (index == 1)
return 1;
else
return fib(index – 1) + fib(index – 2);
Listing 17.2 is a complete program that prompts the user to enter an index and computes the Fibonacci number for the index.
Listing 17.2 ComputeFibonacci.cpp
1 #include <iostream>
2 using namespace std;
3
4 // The function for finding the Fibonacci number
5 int fib(int);
6
7 int main()
8 {
9 // Prompt the user to enter an integer
10 cout << “Enter an index for the Fibonacci number: “;
11 int index;
12 cin >> index;
13
14 // Display factorial
15 cout << “Fibonacci number at index ” << index << ” is ”
16 << fib(index) << endl;
17
18 return 0;
19 }
20
21 // The function for finding the Fibonacci number
22 int fib(int index)
23 {
24 if (index == 0) // Base case
25 return 0;
26 else if (index == 1) // Base case
27 return 1;
28 else // Reduction and recursive calls
29 return fib(index – 1) + fib(index – 2);
30 }
The program does not show the considerable amount of work done behind the scenes by the computer. Figure 17.4, however, shows successive recursive calls for evaluating fib(4). The original function, fib(4), makes two recursive calls, fib(3) and fib(2), and then returns fib(3) + fib(2) But in what order are these functions called? In C++, operands for the binary + operator may be evaluated in any order. Assume it is evaluated from the left to right. The labels in Figure 17.4 show the order in which functions are called.
As shown in Figure 17.4, there are many duplicated recursive calls. For instance, fib(2) is called twice, fib(1) three times, and fib(0) twice. In general, computing fib(index) requires twice as many recursive calls as are needed for computing fib(index – 1). As you try larger index values, the number of calls substantially increases, as shown in Table 17.1.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.