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.

Practice

1. What is the main purpose of using memoization in recursive functions?

easy

A. To avoid using any variables inside the function

B. To store results of expensive function calls and reuse them

C. To convert recursion into iteration automatically

D. To make the function run slower by adding extra steps

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so they don't need to be recalculated.

2. Step 2: Identify the benefit in recursion

   This reduces repeated work and speeds up recursive functions.

3. Final Answer:

   To store results of expensive function calls and reuse them -> Option B

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated results to speed recursion [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with converting recursion to loops
• Believing memoization removes variables

2. Which of the following is the correct way to declare a memoization array for Fibonacci numbers in C?

easy

A. int memo[] = {1, 1};

B. int memo = 100;

C. int memo[100] = {0};

D. int memo(100);

Solution

1. Step 1: Check valid C array declaration

   In C, arrays are declared with type, name, and size in square brackets.

2. Step 2: Identify correct syntax

   int memo[100] = {0}; uses int memo[100] = {0}; which initializes all elements to zero correctly.

3. Final Answer:

   int memo[100] = {0}; -> Option C

4. Quick Check:

   Array declaration with size and initialization = int memo[100] = {0}; [OK]

Hint: Use int array[size] = {0} to initialize memo array [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Assigning a single int instead of an array
• Not initializing the array to zero

3. What will be the output of the following C code snippet using memoization for Fibonacci?

int memo[100] = {0};

int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Trace fib(5) with memoization

   fib(5) = fib(4) + fib(3), and so on, with memo storing results to avoid repeats.

2. Step 2: Calculate Fibonacci values

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect on output
• Mistaking base cases

4. Identify the error in this memoized factorial function in C:

int memo[100] = {0};

int fact(int n) {
  if (n == 0) return 1;
  if (memo[n] != 0) return memo[n];
  memo[n] = n * fact(n - 1);
  return memo[n];
}

int main() {
  printf("%d", fact(5));
  return 0;
}

medium

A. Memo array is not initialized to -1 to detect uncalculated values

B. Base case should return 0 instead of 1

C. Function should use iteration, not recursion

D. Memo array size is too small

Solution

1. Step 1: Understand memo check condition

   The code checks if memo[n] != 0 to decide if value is cached.

2. Step 2: Identify problem with zero initialization

   Since factorial(0) = 1, memo[1] will be 0 initially, but 0 is a valid value for uninitialized. This causes confusion.

3. Step 3: Correct approach

   Initialize memo array with -1 to mark uncalculated values, so 0 is a valid cached result.

4. Final Answer:

   Memo array is not initialized to -1 to detect uncalculated values -> Option A

5. Quick Check:

   Use -1 to mark uncalculated memo entries [OK]

Hint: Initialize memo with -1 to detect uncalculated values [OK]

Common Mistakes:

• Assuming zero means uncalculated without initialization
• Changing base case incorrectly
• Thinking recursion must be replaced by iteration

5. You want to optimize a recursive function that calculates the number of ways to climb n stairs taking 1 or 2 steps at a time. Which memoization approach below correctly stores intermediate results to avoid repeated calculations?

hard

A. Use a global variable to count calls without storing results

B. Recalculate all values each time without storing

C. Use a linked list to store all previous results dynamically

D. Use an array int memo[n+1] initialized with -1, store results at memo[i] for steps i

Solution

1. Step 1: Understand problem and memoization need

   Number of ways to climb stairs is a classic recursion problem with overlapping subproblems.

2. Step 2: Choose correct memoization method

   Using an array sized n+1 initialized with -1 allows storing results for each step count to reuse.

3. Final Answer:

   Use an array int memo[n+1] initialized with -1, store results at memo[i] for steps i -> Option D

4. Quick Check:

   Array memo with -1 initialization stores intermediate results [OK]

Hint: Use array memo[n+1] with -1 to store step results [OK]

Common Mistakes:

• Not initializing memo array properly
• Using global counters without memoization
• Using complex data structures unnecessarily