gen-define-memoization-and-give-one-short-worked-example-6092

Define memoization and give one short worked example.

# Memoization **Memoization** is an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again, avoiding redundant calculations. ## Short Worked Example Computing Fibonacci numbers without memoization repeats work: ```python # Without memoization - SLOW def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # fib(5) calls fib(3) twice, fib(2) three times, etc. ``` **With memoization:** ```python cache = {} def fib(n): if n in cache: return cache[n] # Return cached result if n <= 1: result = n else: result = fib(n-1) + fib(n-2) cache[n] = result # Store for future use return result ``` **Trace for fib(5):** - fib(5) → fib(4) + fib(3) - fib(4) → fib(3) + fib(2) ← fib(3) computed once, then reused - fib(3) → fib(2) + fib(1) ← cached after first computation - Results stored: {0:0, 1:1, 2:1, 3:2, 4:3, 5:5} **Result:** Changes time complexity from O(2ⁿ) to O(n).