- Recursion Versus Iteration
- A More Challenging Example: Rabbit Numbers
- Inception: The True Benefit of Recursion
- The Tower of Hanoi
- Other Aspects of Efficient Algorithms
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
A More Challenging Example: Rabbit Numbers
What’s the best way to calculate the Nth Fibonacci number? This is the famous series of numbers brought from India to Europe by the son of Bonacci (or, in Italian, “Fibonacci”). This number series describes (among a million other things) the growth in population of a pair of rabbits allowed to breed without limit.
There are a couple of issues relevant here to designing and writing a good C++ function.
First, consider data types. If you want to calculate, say, the 60th Fibonacci number, using int or even long int in C++ is inadequate: 32-bit integers provide a range of approximately plus or minus 2 billion… or, if you use unsigned integers, zero to 4 billion. Fibonacci numbers quickly exceed this limitation.
The Fibonacci sequence can make good use of the long long type; the C++11 spec mandates support for this type, but some compiler vendors have supported it for years. A long long is usually a 64-bit integer… providing a range not of 4 billion but the square of that number. (As Carl Sagan would say, “billions and billions!”)
Floating-point numbers provide even larger ranges but are subject to rounding errors. And that, by the way, is why it’s a bad idea to use floating-point for all number storage, as was done in primitive forms of BASIC. Floating-point values tend to be approximations.
You may remember the Fibonacci sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
Mathematically, the sequence is expressed as:
F(0) = 1 F(1) = 1 F(n) = F(n-1) + F(n-2)
Very elegant. Each Fibonacci is formed by adding the two numbers before it in the sequence. It seems like such a perfect case for recursion, because the definition itself is recursive. The obvious way to write the function is:
long long fibo(int n) {
if (n > 1)
return fibo(n-1) + fibo(n-2);
else
return 1;
}
This function is beautiful in its brevity—and also spectacularly inefficient! As n increases, the function calls increase exponentially. By calling fibo(50), you place an astronomical number of function calls on the stack. (Think Carl Sagan again… billions and billions!) One of the reasons this approach is so poor is that it recalculates the same numbers many, many times.
When a straightforward iterative solution is available, it is almost always preferable. Here is the iterative version of Fibonacci-number calculation:
long long fibo(int n) {
int sum = 1;
int temp1 = 1;
int temp2 = 1;
for (int i = 2; i <= n; i++) {
temp1 = temp2;
temp2 = sum;
sum = temp1 + temp2;
}
return sum;
}
This version has more lines of code, and yet it calculates fibo(70) in a fraction of a second rather than hours. In this version, each Fibonacci is calculated only once. Each pass of the loop promotes temp1 and temp2 one position forward in the sequence and then recalculates.
Is there a relatively efficient recursive version? Yes, because any iterative algorithm can be rewritten as a recursive one, and vice versa. We can rewrite the function as a recursive version while keeping the basic strategy of iteration: to calculate each Fibonacci exactly once and then promote each of the variables forward in the sequence.
long long fibo(int n, long long prev1, long long prev2) {
if (n < 2)
return 1;
else if (n == 2)
return prev1 + prev2;
else
return fibo(n-1, prev2, prev1 + prev2);
}
The initial call to fibo() should use the initial values 1, 1. So, to calculate Fibonacci number 5, for example, make the following function call:’
fibo(5, 1, 1);
This version is (potentially) millions of times more efficient than the first recursive version, because the function calls increase in a linear fashion rather than exponentially. In a sense, this version simulates what the iterative version does: It puts the results of each “loop” (or rather virtual loop) on the stack. The number 5, in this case, is an indicator of how many times the “loop” is to be processed. The values 1, 1 are the initial values. The algorithm then moves forward through the Fibonacci series in a reasonably efficient manner.
)
Finally, the last two operands (3 and 5) are added, and the value 8 is then returned all the way down the stack, back to the original function call.
But this version is still less efficient than the iterative version—although marginally less so. It's less efficient because it puts the values on the stack and incurs the cost of function-call overhead rather than just accumulating results in local variables temp1 and temp2.