Return the n-th Fibonacci number where fib(0)=0, fib(1)=1. Unlike the recursion
section, here you must make it efficient with memoization so large n is fast.
fib(n)
Assume n >= 0.
fib(6) // → 8
fib(10) // → 55
fib(40) // → 102334155
The direct translation of fib(n) = fib(n-1) + fib(n-2) into recursive calls works, but it's shockingly slow beyond small n. Trace fib(5): it calls fib(4) and fib(3). But fib(4) itself calls fib(3) and fib(2) — so fib(3) gets computed twice, and the fanning-out compounds further down. The number of calls roughly doubles with each increase in n — O(2ⁿ). By n=40, you're making over a billion redundant calls for a problem with only 40 genuinely distinct answers.
fib(3) always returns the same value no matter which branch asked for it. The recursion tree is full of duplicate work — the same question, "what is fib(k)?", asked over and over with the same k. Answer each distinct question once and remember it, and you eliminate almost all the waste.
That's memoization: keep a cache keyed by the subproblem's input, and check it before doing the recursive work. If already solved, return the stored answer instantly. If not, compute normally, then store the result before returning.
The cached state is just the integer k — "the k-th Fibonacci number." Only n+1 distinct values of k will ever be asked about, so once each is computed and cached, any repeat request is a constant-time lookup — collapsing the exponential blowup to linear time.
fib(0)=0, fib(1)=1).fib(k-1) + fib(k-2), store it under key k, and return it.Since each of the n+1 distinct subproblems is solved exactly once, total work becomes O(n) time, O(n) space for the cache. "Notice recursive calls repeat with identical arguments, then cache by those arguments" is the blueprint for turning naive exponential recursion efficient across almost every DP problem.
def fib(n):
memo = {}
def f(k):
if k < 2:
return k
if k in memo:
return memo[k]
v = f(k - 1) + f(k - 2)
memo[k] = v
return v
return f(n)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.