Here is a simple recursive function to compute the Fibonacci sequence:

/** Recursively generate and return the nth Fibonacci number */ static long fibr(int n) { // fibr(91) is the largest value that fits in a long assert (n > 0) && (n <= 91) : "n out of range"; 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:

/** Iteratively generate and return the nth Fibonacci number */ static long fibi(int n) { // fibr(91) is the largest value that fits in a long assert (n > 0) && (n <= 91) : "n out of range"; 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; i++) { // Compute next value 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.