Easy Base + Memo Recursion
In plain English: Compute the nth Fibonacci number without redundantly recalculating the same sub-values.
Naive recursion recomputes fib(k) exponentially many times — memoization stores each result once, collapsing O(2^n) to O(n).
Prompt
Compute the nth Fibonacci number efficiently.
Try to write it from scratch before scrolling down.
Solution
# Recursive + memo
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2) # store to avoid recomputation
return memo[n]
# Iterative (O(1) space)
def fib_iter(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Test: fib(10) == 55