Memoization to Optimize Recursion in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following C# code that calculates Fibonacci numbers using memoization?

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 (n <= 1) return n;
        if (memo.ContainsKey(n)) return memo[n];
        int result = Fib(n - 1) + Fib(n - 2);
        memo[n] = result;
        return result;
    }

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

A 13

B 15

C 21

D 8

💡 Hint

Remember that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13...

Fib(6) = Fib(5) + Fib(4) = 5 + 3 = 8. Memoization stores intermediate results to avoid repeated calculations.

❓ Predict Output

intermediate

Memoization Cache State After Calls

After calling Fib(5) using the memoized Fibonacci function below, what is the content of the memo dictionary?

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 (n <= 1) return n;
        if (memo.ContainsKey(n)) return memo[n];
        int result = Fib(n - 1) + Fib(n - 2);
        memo[n] = result;
        return result;
    }

    static void Main() {
        Fib(5);
        foreach(var kvp in memo) {
            Console.WriteLine($"{kvp.Key}:{kvp.Value}");
        }
    }
}

A

2:1
3:2
4:3
5:5

B

2:1
3:2
4:3
5:8

C

1:1
2:1
3:2
4:3
5:5

D

1:1
2:2
3:3
4:5
5:8

💡 Hint

Memo stores results only for n > 1 after calculation.

Fib(2)=1, Fib(3)=2, Fib(4)=3, Fib(5)=5 are stored. Fib(1) and Fib(0) are base cases and not stored.

🔧 Debug

advanced

Identify the Bug in Memoized Factorial

What error will the following C# code produce when calling Factorial(5)?

DSA C#

using System;
using System.Collections.Generic;

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

    static int Factorial(int n) {
        if (n == 0) return 1;
        if (memo.ContainsKey(n)) return memo[n];
        int result = n * Factorial(n - 1);
        // Missing memoization store here
        return result;
    }

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

A StackOverflowException

B Output: 120

C KeyNotFoundException

D Output: 0

💡 Hint

Check if memo dictionary is updated after calculation.

Though memo is not updated, the recursion works correctly and returns 120 for Factorial(5). Memoization is not effective but no error occurs.

❓ Predict Output

advanced

Output of Memoized Climbing Stairs Problem

What is the output of the following C# code that uses memoization to count ways to climb stairs?

DSA C#

using System;
using System.Collections.Generic;

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

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

    static void Main() {
        Console.WriteLine(ClimbStairs(4));
    }
}

A 8

B 7

C 5

D 6

💡 Hint

Number of ways to climb 4 steps with 1 or 2 steps at a time.

Ways to climb 4 steps = ways(3) + ways(2) = 3 + 2 = 5.

🧠 Conceptual

expert

Memoization Impact on Recursive Tree Size

Consider a naive recursive function without memoization that computes Fibonacci numbers. How does adding memoization affect the number of recursive calls?

A Changes calls from linear to exponential due to caching

B Increases calls because memo dictionary adds overhead

C Has no effect on number of calls, only on memory usage

D Reduces exponential calls to linear calls by storing intermediate results

💡 Hint

Think about repeated calculations in recursion.

Memoization stores results of subproblems, so each is computed once, reducing calls from exponential to linear.

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