Memoization to Optimize Recursion in DSA C#

Mental Model

Memoization saves answers to problems we already solved so we don't repeat work.

Analogy: Imagine you are solving a puzzle and write down each solved piece on a sticky note. When you see the same piece again, you just look at the note instead of solving it again.

call fib(4)
  ↓
call fib(3) -> call fib(2) -> call fib(1)
  ↑          ↑          ↑
memo: {} (empty at start)

Dry Run Walkthrough

Input: Calculate fib(4) using recursion with memoization

Goal: Find fib(4) efficiently by remembering previous results

Step 1: Call fib(4), check memo (empty), compute fib(3) and fib(2)

memo: {}
fib(4) waits for fib(3) and fib(2)

Why: We need fib(3) and fib(2) to find fib(4)

Step 2: Call fib(3), check memo (empty), compute fib(2) and fib(1)

memo: {}
fib(3) waits for fib(2) and fib(1)

Why: fib(3) depends on fib(2) and fib(1)

Step 3: Call fib(2), check memo (empty), compute fib(1) and fib(0)

memo: {}
fib(2) waits for fib(1) and fib(0)

Why: fib(2) depends on fib(1) and fib(0)

Step 4: fib(1) and fib(0) are base cases, return 1 and 0, store in memo

memo: {1:1, 0:0}
fib(2) can now compute

Why: Base cases give known answers

Step 5: Compute fib(2) = fib(1)+fib(0) = 1+0=1, store in memo

memo: {1:1, 0:0, 2:1}
fib(3) waits for fib(1)

Why: fib(2) result saved to avoid recomputation

Step 6: fib(1) found in memo, return 1 immediately

memo: {1:1, 0:0, 2:1}
fib(3) can now compute

Why: Memoization avoids repeated work

Step 7: Compute fib(3) = fib(2)+fib(1) = 1+1=2, store in memo

memo: {1:1, 0:0, 2:1, 3:2}
fib(4) waits for fib(2)

Why: fib(3) result saved

Step 8: fib(2) found in memo, return 1 immediately

memo: {1:1, 0:0, 2:1, 3:2}
fib(4) can now compute

Why: Memoization saves time

Step 9: Compute fib(4) = fib(3)+fib(2) = 2+1=3, store in memo

memo: {1:1, 0:0, 2:1, 3:2, 4:3}
Result fib(4) = 3

Why: Final answer computed efficiently

Result:

memo: {0:0, 1:1, 2:1, 3:2, 4:3}
Fib(4) = 3

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static Dictionary<int, int> memo = new Dictionary<int, int>();

    static int Fib(int n)
    {
        if (memo.ContainsKey(n))
            return memo[n]; // return saved result to avoid recomputation

        if (n <= 1)
            return n; // base case: fib(0)=0, fib(1)=1

        int result = Fib(n - 1) + Fib(n - 2); // recursive calls
        memo[n] = result; // save result for future calls
        return result;
    }

    static void Main()
    {
        int n = 4;
        int answer = Fib(n);
        Console.WriteLine($"Fib({n}) = {answer}");
    }
}

if (memo.ContainsKey(n)) return memo[n];

return saved result to avoid recomputation

if (n <= 1) return n;

handle base cases directly

int result = Fib(n - 1) + Fib(n - 2);

recursive calls to smaller subproblems

memo[n] = result;

save computed result for memoization

Output

Fib(4) = 3

Complexity Analysis

Time: O(n) because each number from 0 to n is computed once and saved

Space: O(n) for the memo dictionary storing results for each number up to n

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

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA C#

if (n <= 1)
    return n;

n = 1 (smallest non-zero input)

Returns 1 immediately as base case

DSA C#

if (n <= 1)
    return n;

Repeated calls with same n

Returns memoized result instantly without recursion

DSA C#

if (memo.ContainsKey(n))
    return memo[n];

When to Use This Pattern

When you see a recursive problem with overlapping subproblems, reach for memoization to save repeated work and speed up the solution.

Common Mistakes

Mistake: Not storing the computed result in the memo dictionary after recursion
Fix: Add memo[n] = result; after computing the recursive result

Mistake: Not checking the memo dictionary before recursive calls
Fix: Check if result exists in memo before recursion to avoid repeated calls

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 save and reuse answers instead of recomputing them.

Practice

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

easy

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

B. To avoid using any variables inside the function

C. To convert recursion into iteration automatically

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

Solution

1. Step 1: Understand recursion inefficiency

   Recursive functions often repeat the same calculations multiple times, which wastes time.

2. Step 2: Role of memoization

   Memoization saves the results of these repeated calculations so they can be reused instead of recalculated.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

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

Common Mistakes:

• Thinking memoization slows down recursion
• Confusing memoization with iteration
• Believing memoization removes recursion

2. Which of the following is the correct way to declare a memo dictionary for integer keys and values in C#?

easy

A. HashSet memo = new HashSet();

B. List memo = new List();

C. Dictionary memo = new Dictionary();

D. Dictionary memo = new Dictionary();

Solution

1. Step 1: Identify correct generic dictionary syntax

   In C#, a dictionary with integer keys and values is declared as Dictionary.

2. Step 2: Check options for correct syntax

   Dictionary memo = new Dictionary(); uses Dictionary with proper initialization, others use wrong types or missing generics.

3. Final Answer:

   Dictionary memo = new Dictionary(); -> Option C

4. Quick Check:

   Dictionary = Correct memo declaration [OK]

Hint: Use Dictionary for integer key-value memo [OK]

Common Mistakes:

• Using List or HashSet instead of Dictionary
• Missing generic type parameters
• Using untyped Dictionary without generics

3. What will be the output of the following C# code?

using System;
using System.Collections.Generic;

class Program {
    static Dictionary memo = new Dictionary();

    static int Fib(int n) {
        if (n <= 1) return n;
        if (memo.ContainsKey(n)) return memo[n];
        memo[n] = Fib(n - 1) + Fib(n - 2);
        return memo[n];
    }

    static void Main() {
        Console.WriteLine(Fib(5));
    }
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci calculation

   Fib(5) = Fib(4) + Fib(3). Calculating recursively with memoization avoids repeated work.

2. Step 2: Calculate Fib(5) step-by-step

   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: Recall Fibonacci sequence values or trace memoized calls [OK]

Common Mistakes:

• Confusing Fib(5) with Fib(6)
• Ignoring memoization effect
• Miscounting base cases

4. Identify the error in this memoized factorial function and select the fix:

static Dictionary memo = new Dictionary();

static int Factorial(int n) {
    if (n == 0) return 1;
    if (memo.ContainsKey(n)) return memo[n];
    memo[n] = n * Factorial(n - 1);
    return n;
}

medium

A. Use memo[n] = Factorial(n - 1) * (n - 1);

B. Return memo[n] instead of n after recursive call

C. Remove memo dictionary completely

D. Change base case to if (n == 1) return 1;

Solution

1. Step 1: Analyze return statement after recursion

   The function returns 'n' instead of the computed factorial stored in memo[n], which is incorrect.

2. Step 2: Correct return value

   Return memo[n] to return the calculated factorial value after storing it.

3. Final Answer:

   Return memo[n] instead of n after recursive call -> Option B

4. Quick Check:

   Return memo[n] fixes incorrect output [OK]

Hint: Return stored memo value, not input parameter [OK]

Common Mistakes:

• Returning input parameter instead of memoized result
• Changing base case unnecessarily
• Misusing memo dictionary keys

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 implements this in C#?

hard

A. Use a Dictionary to store results; base cases for 0 and 1 stairs return 1; recursive call sums ways(n-1) and ways(n-2).

B. Use a List<int> to store results; base case returns 0 for 0 stairs; recursive call multiplies ways(n-1) and ways(n-2).

C. Use a Dictionary but no base cases; recursive call sums ways(n-1) and ways(n-2).

D. Use an array of size n; base cases return n; recursive call subtracts ways(n-1) from ways(n-2).

Solution

1. Step 1: Understand problem and base cases

   Number of ways to climb stairs with 1 or 2 steps: ways(0)=1 (one way to stand still), ways(1)=1.

2. Step 2: Correct memoization approach

   Use Dictionary to store results; recursive call sums ways(n-1) and ways(n-2) to count all paths.

3. Final Answer:

   Use a Dictionary to store results; base cases for 0 and 1 stairs return 1; recursive call sums ways(n-1) and ways(n-2). -> Option A

4. Quick Check:

   Memo + base cases + sum recursion = Use a Dictionary to store results; base cases for 0 and 1 stairs return 1; recursive call sums ways(n-1) and ways(n-2). [OK]

Hint: Base cases 0,1 = 1; sum ways(n-1) + ways(n-2) with memo [OK]

Common Mistakes:

• Wrong base cases values
• Using multiplication instead of addition
• Missing base cases causing infinite recursion