Fibonacci, from exponential to linear

Question

The naive recursive Fibonacci takes seconds for n = 35 and effectively never finishes for n = 60. Explain why the naive version is exponential, then fix it. Aim for O(n).

Accepted Answer

The recursion tree recomputes the same subproblems over and over: fib(n) calls fib(n-2) twice (once directly, once inside fib(n-1)), and the duplication compounds, the call count grows like \phi^n where \phi \approx 1.618. But there are only n+1 distinct subproblems. Caching each result the first time it is computed (memoization) collapses the tree to O(n) calls. Even better, walk bottom-up and keep only the last two values, O(n) time, O(1) space, and no recursion-depth limit: Check: fibiter(10) returns 55. An interviewer may push further: fast matrix exponentiation of \begin{pmatrix}1&1\1&0…

Fibonacci, from exponential to linear

Your answer

More Coding questions