A function fib(n) for Fibonacci numbers is defined recursively as “if n is 1 or less, return n; otherwise return fib(n−1) + fib(n−2)”. When fib(5) is called, how many times is fib called, including the first call?

Answer: C. 15

Let C(n) be the number of calls for fib(n). Then C(0) = C(1) = 1 and C(n) = 1 + C(n−1) + C(n−2), so C(2) = 3, C(3) = 5, C(4) = 9 and C(5) = 15. Because the same values are recomputed again and again, the count grows exponentially with n; fib(30) makes about 2.69 million calls. With memoization (a form of dynamic programming), which stores computed values in a table, only the six values fib(0) to fib(5) are computed and the calls drop to 9 (2n − 1). 6 is the number of distinct arguments, and 9 is the number of calls with memoization.

• A. This is the number of distinct arguments fib(0) to fib(5); it does not count recomputation of the same values.
• B. This is the number of calls with memoization, where a value already computed is returned from a table.
• C. Correct. From C(n) = 1 + C(n−1) + C(n−2), C(5) = 15.