Memoization to Optimize Recursion in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of recursion?

Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does memoization improve the performance of recursive functions?

It saves the results of recursive calls in a cache (like an array or dictionary) so that each unique call is computed only once, reducing time complexity from exponential to linear in many cases.

intermediate

In C, what data structure is commonly used to implement memoization for recursion?

An array or a hash table (if keys are not simple integers) is commonly used to store computed results for memoization in C.

intermediate

What is the difference between memoization and dynamic programming?

Memoization is a top-down approach that caches results of recursive calls, while dynamic programming is often a bottom-up approach that builds solutions iteratively. Both avoid repeated work but differ in implementation style.

beginner

Why is memoization especially useful in problems like Fibonacci sequence calculation?

Because naive recursion recalculates the same Fibonacci numbers many times, memoization stores these results once computed, drastically reducing the number of calls and improving efficiency.

What does memoization store to optimize recursion?

A Previously computed results

B Input parameters only

C Function call stack

D Random values

Memoization stores previously computed results to avoid recalculating them.

Which data structure is commonly used for memoization in C when inputs are integers?

A Linked list

B Queue

C Stack

D Array

Arrays are commonly used to store memoized results indexed by integer inputs.

Memoization changes the time complexity of naive Fibonacci recursion from exponential to what?

A Quadratic

B Linear

C Logarithmic

D Constant

Memoization reduces Fibonacci recursion time complexity to linear by caching results.

Memoization is an example of which programming technique?

A Greedy algorithm

B Bottom-up dynamic programming

C Top-down dynamic programming

D Divide and conquer without caching

Memoization is a top-down approach that caches recursive calls.

What happens if memoization is not used in recursive functions with overlapping subproblems?

A The function recalculates the same results multiple times

B The function runs faster

C The function uses less memory

D The function never terminates

Without memoization, recursive functions with overlapping subproblems recompute results repeatedly.

Explain how memoization optimizes a recursive function using the Fibonacci sequence as an example.

Think about how many times the same Fibonacci number is calculated without memoization.

Describe the steps to implement memoization in a recursive C function.

Focus on how to avoid repeated work by checking and storing results.

Practice

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

easy

A. To avoid using any variables inside the function

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

C. To convert recursion into iteration automatically

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

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so they don't need to be recalculated.

2. Step 2: Identify the benefit in recursion

   This reduces repeated work and speeds up recursive functions.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

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

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with converting recursion to loops
• Believing memoization removes variables

2. Which of the following is the correct way to declare a memoization array for Fibonacci numbers in C?

easy

A. int memo[] = {1, 1};

B. int memo = 100;

C. int memo[100] = {0};

D. int memo(100);

Solution

1. Step 1: Check valid C array declaration

   In C, arrays are declared with type, name, and size in square brackets.

2. Step 2: Identify correct syntax

   int memo[100] = {0}; uses int memo[100] = {0}; which initializes all elements to zero correctly.

3. Final Answer:

   int memo[100] = {0}; -> Option C

4. Quick Check:

   Array declaration with size and initialization = int memo[100] = {0}; [OK]

Hint: Use int array[size] = {0} to initialize memo array [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Assigning a single int instead of an array
• Not initializing the array to zero

3. What will be the output of the following C code snippet using memoization for Fibonacci?

int memo[100] = {0};

int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Trace fib(5) with memoization

   fib(5) = fib(4) + fib(3), and so on, with memo storing results to avoid repeats.

2. Step 2: Calculate Fibonacci values

   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: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect on output
• Mistaking base cases

4. Identify the error in this memoized factorial function in C:

int memo[100] = {0};

int fact(int n) {
  if (n == 0) return 1;
  if (memo[n] != 0) return memo[n];
  memo[n] = n * fact(n - 1);
  return memo[n];
}

int main() {
  printf("%d", fact(5));
  return 0;
}

medium

A. Memo array is not initialized to -1 to detect uncalculated values

B. Base case should return 0 instead of 1

C. Function should use iteration, not recursion

D. Memo array size is too small

Solution

1. Step 1: Understand memo check condition

   The code checks if memo[n] != 0 to decide if value is cached.

2. Step 2: Identify problem with zero initialization

   Since factorial(0) = 1, memo[1] will be 0 initially, but 0 is a valid value for uninitialized. This causes confusion.

3. Step 3: Correct approach

   Initialize memo array with -1 to mark uncalculated values, so 0 is a valid cached result.

4. Final Answer:

   Memo array is not initialized to -1 to detect uncalculated values -> Option A

5. Quick Check:

   Use -1 to mark uncalculated memo entries [OK]

Hint: Initialize memo with -1 to detect uncalculated values [OK]

Common Mistakes:

• Assuming zero means uncalculated without initialization
• Changing base case incorrectly
• Thinking recursion must be replaced by iteration

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 stores intermediate results to avoid repeated calculations?

hard

A. Use a global variable to count calls without storing results

B. Recalculate all values each time without storing

C. Use a linked list to store all previous results dynamically

D. Use an array int memo[n+1] initialized with -1, store results at memo[i] for steps i

Solution

1. Step 1: Understand problem and memoization need

   Number of ways to climb stairs is a classic recursion problem with overlapping subproblems.

2. Step 2: Choose correct memoization method

   Using an array sized n+1 initialized with -1 allows storing results for each step count to reuse.

3. Final Answer:

   Use an array int memo[n+1] initialized with -1, store results at memo[i] for steps i -> Option D

4. Quick Check:

   Array memo with -1 initialization stores intermediate results [OK]

Hint: Use array memo[n+1] with -1 to store step results [OK]

Common Mistakes:

• Not initializing memo array properly
• Using global counters without memoization
• Using complex data structures unnecessarily