Memoization to Optimize Recursion in DSA C

Mental Model

Memoization saves answers to small problems so we don't solve them again.

Analogy: Like writing down answers to math problems on a cheat sheet to avoid redoing the same work.

fib(5)
  ↓
fib(4) + fib(3)
 ↓       ↓
fib(3)+fib(2) fib(2)+fib(1)
 ↑
Cache stores fib(3), fib(2), fib(1) results

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Find fib(5) efficiently by storing results of fib(n) to avoid repeated work

Step 1: Call fib(5), cache empty

Cache: {}
Call stack: fib(5)

Why: Start calculation for fib(5)

Step 2: Call fib(4) from fib(5), cache still empty

Cache: {}
Call stack: fib(5) -> fib(4)

Why: Need fib(4) to compute fib(5)

Step 3: Call fib(3) from fib(4), cache still empty

Cache: {}
Call stack: fib(5) -> fib(4) -> fib(3)

Why: Need fib(3) to compute fib(4)

Step 4: Call fib(2) from fib(3), cache still empty

Cache: {}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(2)

Why: Need fib(2) to compute fib(3)

Step 5: fib(2) base case returns 1, store in cache

Cache: {2:1}
Call stack: fib(5) -> fib(4) -> fib(3)

Why: fib(2) known, save result

Step 6: Call fib(1) from fib(3), base case returns 1, store in cache

Cache: {2:1, 1:1}
Call stack: fib(5) -> fib(4) -> fib(3)

Why: fib(1) known, save result

Step 7: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store in cache

Cache: {2:1, 1:1, 3:2}
Call stack: fib(5) -> fib(4)

Why: fib(3) computed and saved

Step 8: Call fib(2) from fib(4), found in cache as 1

Cache: {2:1, 1:1, 3:2}
Call stack: fib(5) -> fib(4)

Why: Reuse cached fib(2) to avoid recomputation

Step 9: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store in cache

Cache: {2:1, 1:1, 3:2, 4:3}
Call stack: fib(5)

Why: fib(4) computed and saved

Step 10: Call fib(3) from fib(5), found in cache as 2

Cache: {2:1, 1:1, 3:2, 4:3}
Call stack: fib(5)

Why: Reuse cached fib(3) to avoid recomputation

Step 11: Calculate fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store in cache

Cache: {2:1, 1:1, 3:2, 4:3, 5:5}
Call stack: empty

Why: fib(5) computed and saved, recursion ends

Result:

Cache: {1:1, 2:1, 3:2, 4:3, 5:5}
Answer: 5

Annotated Code

DSA C

#include <stdio.h>

#define MAX 100

int cache[MAX];

int fib(int n) {
    if (n <= 1) return 1; // base case
    if (cache[n] != 0) return cache[n]; // return cached result
    cache[n] = fib(n - 1) + fib(n - 2); // compute and cache
    return cache[n];
}

int main() {
    int n = 5;
    for (int i = 0; i < MAX; i++) cache[i] = 0; // initialize cache
    int result = fib(n);
    printf("fib(%d) = %d\n", n, result);
    return 0;
}

if (n <= 1) return 1; // base case

Return 1 for fib(0) and fib(1) as base cases

if (cache[n] != 0) return cache[n]; // return cached result

Return cached result if already computed to avoid repeated work

cache[n] = fib(n - 1) + fib(n - 2); // compute and cache

Compute fib(n) recursively and store result in cache

Output

fib(5) = 5

Complexity Analysis

Time: O(n) because each fib(n) is computed once and then reused from cache

Space: O(n) for the cache array storing results for each n up to input

vs Alternative: Without memoization, time is O(2^n) due to repeated calls; memoization reduces this to linear time

Edge Cases

n = 0 or n = 1 (base cases)

Returns 1 immediately without recursion

DSA C

if (n <= 1) return 1; // base case

n larger than cache size

May cause out-of-bounds access; code assumes n < MAX

DSA C

No explicit guard; user must ensure n < MAX

Repeated calls with same n

Returns cached result instantly, no recomputation

DSA C

if (cache[n] != 0) return cache[n]; // return cached result

When to Use This Pattern

When you see a recursive problem with overlapping subproblems, use memoization to save results and avoid repeated work.

Common Mistakes

Mistake: Not checking cache before recursive calls, causing repeated computations
Fix: Add a cache check before recursion to return stored results immediately

Mistake: Not initializing cache to zero, causing incorrect cache hits
Fix: Initialize cache array to zero before starting recursion

Summary

Memoization stores results of recursive calls to avoid repeating work.

Use it when recursion solves the same subproblems multiple times.

The key is to check and save answers so each subproblem is solved once.