Module 2: Memoization (The Cheat Sheet)

📚 Module 2: Memoization

Course ID: DSA-204
Subject: The Cheat Sheet

Recursion is powerful but often very slow. Why? Because it often recalculates the same thing over and over. We fix this with Memoization.

🏗️ Step 1: The Redundancy Problem

Imagine calculating the 50th Fibonacci number.

To find #50, you need #49 and #48.
To find #49, you need #48 and #47.
Wait! You just asked for #48 twice!
By the time you reach the end, you’ve asked for #1 billions of times. This takes years.

🏗️ Step 2: Memoization (The “Cheat Sheet”)

Memoization is simply writing down the answer as soon as you find it.

🧩 The Analogy: The Math Quiz

Standard Recursion: Every time the teacher asks “What is 5x5?”, you pull out 25 apples and count them one by one.
Memoization: The first time you’re asked, you count the apples. You write “5x5 = 25” on a Sticky Note (A Map/Dictionary). Next time the teacher asks, you just look at the note!

🏗️ Step 3: In Code (Python)

cache = {} # Our sticky note

def fib(n):
    # 1. Check the sticky note first!
    if n in cache:
        return cache[n]
    
    # 2. Base case
    if n <= 1:
        return n
    
    # 3. Calculate and SAVE to the note
    result = fib(n - 1) + fib(n - 2)
    cache[n] = result
    
    return result

🥅 Module 2 Review

Memoization: Storing results of expensive function calls.
Trade-off: We use a little more Space (The Cache) to save a lot of Time.
Efficiency: This turns an “Exponential” problem ( $O(2^n)$ ) into a “Linear” problem ( $O(n)$ ).

:::tip Senior Tip In Python, you don’t even need to write the cache yourself. You can use the @lru_cache decorator to do it automatically! ::: Riverside. Riverside.