Here is a simple recursive function to compute the Fibonacci sequence:
// Recursive Fibonacci generator
static long fibr(int n) {
// fibr(91) is the largest value that fits in a long
assert (n > 0) && (n <=>
if ((n == 1) || (n == 2)) return 1; // Base case
return fibr(n-1) + fibr(n-2); // Recursive call
}
This algorithm turns out to be very slow, calling Fibr a total of Fib(n) times. Contrast this with the following iterative algorithm:
// Iterative Fibonacci generator
static long fibi(int n) {
// fibr(91) is the largest value that fits in a long
assert (n > 0) && (n <=>
long curr, prev, past;
if ((n == 1) || (n == 2)) return 1;
curr = prev = 1; // curr holds current Fib value
for (int i=3; i<=n;>
past = prev; // past holds fibi(i-2)
prev = curr; // prev holds fibi(i-1)
curr = past + prev; // curr now holds fibi(i)
}
return curr;
}
Function Fibi executes the for loop n − 2 times.
(a) Which version is easier to understand? Why?
(b) Explain why Fibr is so much slower than Fibi.