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 uses memoization to compute Fibonacci numbers?

DSA C

#include <stdio.h>

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

int main() {
    int n = 5;
    int memo[6];
    for (int i = 0; i <= n; i++) memo[i] = -1;
    int result = fib(n, memo);
    printf("%d\n", result);
    return 0;
}

A 5

B 8

C 13

D 3

💡 Hint

Recall that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5...

The 5th Fibonacci number (0-based index) is 5. The memo array stores intermediate results to avoid repeated calculations.

🧠 Conceptual

intermediate

Memoization Purpose in Recursion

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

A To store intermediate results and avoid repeated calculations

B To make the code shorter and easier to read

C To increase the number of recursive calls

D To convert recursion into iteration automatically

💡 Hint

Think about how recursion can repeat the same work multiple times.

Memoization saves results of expensive function calls and returns the cached result when the same inputs occur again, improving efficiency.

🔧 Debug

advanced

Identify the Error in Memoized Fibonacci

What error will occur when running this code snippet?

DSA C

#include <stdio.h>

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

int main() {
    int n = 5;
    int memo[6] = {0};
    int result = fib(n, memo);
    printf("%d\n", result);
    return 0;
}

A The code prints 0 because memo array is initialized with zeros

B The code runs correctly and prints 5

C The code causes a segmentation fault

D The code prints 1 instead of 5

💡 Hint

Check how memo array is initialized and how memo[n] is checked before recursion.

Since Fibonacci numbers are positive and fib(0)=0, using 0 as uninitialized marker works. The code correctly computes fib(5)=5.

❓ Predict Output

advanced

Output of Factorial with Memoization

What is the output of this C program that uses memoization to compute factorial?

DSA C

#include <stdio.h>

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

int main() {
    int n = 4;
    int memo[5] = {0};
    int result = fact(n, memo);
    printf("%d\n", result);
    return 0;
}

A 120

B 10

C 0

D 24

💡 Hint

Recall factorial 4! = 4*3*2*1

The factorial of 4 is 24. Memoization stores intermediate factorial values to avoid repeated calculations.

🚀 Application

expert

Memoization Impact on Time Complexity

Consider a naive recursive function to compute Fibonacci numbers with exponential time complexity. After adding memoization, what is the new time complexity?

A O(2^n)

B O(n^2)

C O(n)

D O(log n)

💡 Hint

Memoization avoids repeated calls by storing results.

Memoization reduces the exponential time complexity O(2^n) of naive recursion to linear O(n) by caching results.