Given a non-negative integer n, compute the nth Fibonacci number, where fib(0)=0, fib(1)=1, and every later term is the sum of the two before it. Translating the definition straight into recursion works, but it hides a costly flaw: the same smaller Fibonacci values get recomputed from absolute scratch every time a different branch of the recursion happens to need them again — fib(3) might get fully recalculated two, three, or many more times while computing fib(n) for a larger n, and the redundancy compounds exponentially as n grows. Memoization fixes this without changing the recursive structure at all: cache each answer the first time it's computed, and check the cache before doing any real work. Since there are only n+1 distinct subproblems total, and each now gets solved exactly once, the cost collapses from exponential to linear.