Memoization to Optimize Recursion in DSA C# - Execution Trace

Concept Flow - Memoization to Optimize Recursion

Start Recursive Call

↓

Check Memo: Result Exists?

Yes→Return Memoized Result

No↓

Compute Result Recursively

↓

Store Result in Memo

↓

Return Result

↓

End Call

The flow shows how recursion first checks if a result is already saved (memoized). If yes, it returns it immediately. Otherwise, it computes, saves, and returns the result.

Execution Sample

DSA C#

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

This code calculates Fibonacci numbers using recursion with memoization to avoid repeated calculations.

Execution Table

Step	Operation	Current n	Memo Content	Call Stack Depth	Returned Value	Visual State
1	Call Fib(4)	4	{}	1		Fib(4) called, memo empty
2	Check memo for 4	4	{}	1	No	No memo for 4, proceed
3	Call Fib(3)	3	{}	2		Fib(3) called
4	Check memo for 3	3	{}	2	No	No memo for 3
5	Call Fib(2)	2	{}	3		Fib(2) called
6	Check memo for 2	2	{}	3	No	No memo for 2
7	Call Fib(1)	1	{}	4		Fib(1) called
8	Check memo for 1	1	{}	4	No	No memo for 1
9	Base case n<=1	1	{}	4	1	Return 1
10	Return to Fib(2)	2	{}	3		Fib(1) returned 1
11	Call Fib(0)	0	{}	4		Fib(0) called
12	Check memo for 0	0	{}	4	No	No memo for 0
13	Base case n<=1	0	{}	4	0	Return 0
14	Return to Fib(2)	2	{}	3		Fib(0) returned 0
15	Compute Fib(2)	2	{}	3	1	1 + 0 = 1
16	Store memo[2] = 1	2	{2:1}	3		Memo updated with 2:1
17	Return Fib(2)	2	{2:1}	3	1	Return 1
18	Return to Fib(3)	3	{2:1}	2		Fib(2) returned 1
19	Call Fib(1)	1	{2:1}	3		Fib(1) called again
20	Check memo for 1	1	{2:1}	3	No	No memo for 1
21	Base case n<=1	1	{2:1}	3	1	Return 1
22	Return to Fib(3)	3	{2:1}	2		Fib(1) returned 1
23	Compute Fib(3)	3	{2:1}	2	2	1 + 1 = 2
24	Store memo[3] = 2	3	{2:1,3:2}	2		Memo updated with 3:2
25	Return Fib(3)	3	{2:1,3:2}	2	2	Return 2
26	Return to Fib(4)	4	{2:1,3:2}	1		Fib(3) returned 2
27	Call Fib(2)	2	{2:1,3:2}	2		Fib(2) called again
28	Check memo for 2	2	{2:1,3:2}	2	Yes	Memo hit: return 1
29	Return Fib(2)	2	{2:1,3:2}	2	1	Return 1 from memo
30	Compute Fib(4)	4	{2:1,3:2}	1	3	2 + 1 = 3
31	Store memo[4] = 3	4	{2:1,3:2,4:3}	1		Memo updated with 4:3
32	Return Fib(4)	4	{2:1,3:2,4:3}	1	3	Return 3
33	End		{2:1,3:2,4:3}	0		All calls complete

💡 Fib(4) completes after all recursive calls return and memo stores results

Variable Tracker

Variable	Start	After Step 16	After Step 24	After Step 31	Final
n	4	2	3	4	4
memo	{}	{2:1}	{2:1,3:2}	{2:1,3:2,4:3}	{2:1,3:2,4:3}
Call Stack Depth	1	3	2	1	0
Returned Value		1	2	3	3

Key Moments - 3 Insights

Why does the function check the memo dictionary before computing?

Because as shown in steps 2, 4, 6, and 28, checking memo avoids repeating work by returning stored results immediately.

Why do some calls return immediately without further recursion?

Base cases like n <= 1 (steps 9 and 13) return directly to stop infinite recursion and provide known results.

How does memoization reduce the number of recursive calls?

Memoization stores results (steps 16, 24, 31) so repeated calls like Fib(2) at step 27 return instantly (step 28), skipping deeper recursion.

Visual Quiz - 3 Questions

Look at the execution table, what is the memo content after step 24?

A {2:1,3:2}

B {2:1}

C {}

D {2:1,3:2,4:3}

💡 Hint

Check the 'Memo Content' column at step 24 in the execution table.

At which step does Fib(2) return a memoized result instead of computing it again?

A Step 6

B Step 16

C Step 28

D Step 31

💡 Hint

Look for a memo hit for n=2 in the 'Operation' and 'Returned Value' columns.

If the base case was changed to n < 1 instead of n <= 1, what would happen at step 9?

A Fib(1) would return 1 as before

B Fib(1) would recurse further causing errors

C Fib(0) would return 0 as before

D Memo would store incorrect values

💡 Hint

Check the base case condition and what happens when n=1 at step 9.

Concept Snapshot

Memoization stores results of recursive calls in a dictionary.
Before computing, check if result exists to avoid repeated work.
Base cases stop recursion.
Memo updates happen after computing new results.
This reduces exponential calls to linear time.

Full Transcript

Memoization optimizes recursion by saving results of function calls in a dictionary called memo. When the function is called with a value, it first checks if the result is already in memo. If yes, it returns that result immediately, skipping further recursion. If not, it computes the result recursively, stores it in memo, and returns it. Base cases like n <= 1 stop recursion by returning known values. This technique reduces repeated calculations and speeds up recursive functions like Fibonacci.

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