Fibonacci (naive)
The naive recursion recomputes the same subproblems exponentially many times — fib(2) appears again and again in the call tree. The motivating example for memoization.
- Category
- Recursion
- Time complexity
- O(2ⁿ) (O(2ⁿ) is a valid but loose upper bound. The tight bound on the call count is O(φⁿ) ≈ O(1.618ⁿ), since each call branches into two smaller, unequal subproblems rather than a full binary tree.)
- Space complexity
- O(n)
Pseudocode
if n ≤ 1: return n (no cache — recompute everything) return fib(n−1) + fib(n−2) result
Reference implementation
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
# duplicate subtrees everywhere!