Memoization to Optimize Recursion in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the memo dictionary for caching results.

DSA C#

Dictionary<int, int> memo = new Dictionary<int, int>[1];

Drag options to blanks, or click blank then click option'

A<>

B()

C[]

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses () instead of curly braces {}

Using square brackets [] which are for arrays or lists

Using angle brackets <> which are for generics

The dictionary is initialized with curly braces {} to create an empty dictionary.

2fill in blank

medium

Complete the code to check if the result for n is already computed in memo.

DSA C#

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

Drag options to blanks, or click blank then click option'

AExists

BHasKey

CContainsKey

DContains

Attempts:

3 left

💡 Hint

Common Mistakes

Using HasKey which does not exist in C# Dictionary

Using Exists which is for lists

Using Contains which checks for values, not keys

ContainsKey is the correct method to check if a key exists in a Dictionary in C#.

3fill in blank

hard

Fix the error in the recursive call to use memoization properly.

DSA C#

memo[n] = Fibonacci([1], memo) + Fibonacci(n - 2, memo);

Drag options to blanks, or click blank then click option'

An - 1

Bn

Cn - 2

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n - 1 causes infinite recursion

Using n - 2 twice misses the n - 1 term

Using n + 1 goes beyond the current number

The recursive call should use n - 1 to get the previous Fibonacci number correctly.

4fill in blank

hard

Fill both blanks to complete the Fibonacci method signature and base case check.

DSA C#

public int Fibonacci([1] n, Dictionary<int, int> memo) {
    if ([2]) return n;
    // rest of code
}

Drag options to blanks, or click blank then click option'

Aint

Bn <= 1

Cn == 1

Dbool

Attempts:

3 left

💡 Hint

Common Mistakes

Using bool as parameter type instead of int

Checking only n == 1 misses the case n == 0

Using n < 0 which is invalid for Fibonacci

The method takes an int n, and the base case checks if n is less than or equal to 1 to return n.

5fill in blank

hard

Fill all three blanks to complete the memoization logic inside the Fibonacci method.

DSA C#

if (!memo.ContainsKey(n)) {
    memo[[1]] = Fibonacci(n - 1, [2]) + Fibonacci([3], memo);
}
return memo[n];

Drag options to blanks, or click blank then click option'

An

Bmemo

Cn - 2

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 which is incorrect for Fibonacci

Not passing memo in recursive calls

Using wrong keys for memo dictionary

We store the result for n in memo[n], call Fibonacci with n - 1 and pass memo, then call Fibonacci with n - 2 and memo.

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