Memoization to Optimize Recursion in DSA C# - Build from Scratch

Memoization to Optimize Recursion

📖 Scenario: Imagine you want to calculate the Fibonacci numbers, which are a sequence where each number is the sum of the two before it. Calculating them with simple recursion can be slow because it repeats the same calculations many times.Memoization is a way to remember results of calculations so you don't repeat work. This project will help you learn how to use memoization to make recursion faster.

🎯 Goal: You will build a C# program that calculates Fibonacci numbers using recursion with memoization. This will store already calculated Fibonacci numbers in a dictionary to avoid repeated work.

📋 What You'll Learn

Create a dictionary to store calculated Fibonacci numbers.

Create a recursive function that uses the dictionary to return Fibonacci numbers.

Add a base case for the recursion.

Print the Fibonacci number for a given input.

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world applications like dynamic programming, caching results in web servers, and optimizing complex calculations in games and simulations.

💼 Career

Understanding memoization helps in writing efficient algorithms, which is a key skill for software developers, especially in roles involving performance optimization and algorithm design.

1

Create the memoization dictionary

Create a dictionary called memo of type Dictionary<int, int> and initialize it as empty.

DSA C#

# Your code here
// Create the memo dictionary

Hint

Use Dictionary<int, int> and initialize it with new Dictionary<int, int>().

2

Add the Fibonacci function with base cases

Create a static method called Fibonacci that takes an int n and returns an int. Add base cases: return n if n is 0 or 1.

DSA C#

using System;
using System.Collections.Generic;

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

    static int Fibonacci(int n)
    {
        // Add base cases here
        // Your code here
    }

    static void Main()
    {
    }
}

Hint

Check if n is 0 or 1, then return n.

3

Add memoization logic to the Fibonacci function

In the Fibonacci method, first check if memo contains the key n. If yes, return memo[n]. Otherwise, calculate the Fibonacci number recursively by calling Fibonacci(n - 1) and Fibonacci(n - 2), add them, store the result in memo[n], and return it.

DSA C#

using System;
using System.Collections.Generic;

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

    static int Fibonacci(int n)
    {
        if (n == 0 || n == 1)
        {
            return n;
        }

        // Check if memo contains n
        // If yes, return memo[n]
        // Otherwise, calculate recursively and store in memo[n]
        // Your code here
    }

    static void Main()
    {
    }
}

Hint

Use memo.ContainsKey(n) to check if the value is already calculated.

If not, calculate recursively and store the result in memo[n].

4

Print the Fibonacci number for n = 10

In the Main method, call Fibonacci(10) and print the result using Console.WriteLine.

DSA C#

using System;
using System.Collections.Generic;

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

    static int Fibonacci(int n)
    {
        if (n == 0 || n == 1)
        {
            return n;
        }

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

        int result = Fibonacci(n - 1) + Fibonacci(n - 2);
        memo[n] = result;
        return result;
    }

    static void Main()
    {
        // Print Fibonacci(10) here
        // Your code here
    }
}

Hint

Use Console.WriteLine(Fibonacci(10)); to print the result.

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