Why Dynamic Programming and When Recursion Alone Fails in DSA C - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Without Memoization

What is the output of the following C code that calculates Fibonacci numbers using simple recursion without any optimization?

DSA C

#include <stdio.h>

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

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

A 5

B 8

C 13

D 3

💡 Hint

Recall the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, ...

fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5. The code outputs 5.

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of this C code that calculates Fibonacci numbers using recursion with memoization?

DSA C

#include <stdio.h>

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\n", fib(10));
    return 0;
}

A 55

B 89

C 34

D 144

💡 Hint

Remember fib(10) in Fibonacci sequence starting from fib(0)=0.

The 10th Fibonacci number (starting at fib(0)=0) is 55. Memoization avoids repeated calculations, so the function returns 55 efficiently.

🧠 Conceptual

advanced

Why Recursion Alone Can Be Inefficient

Why does simple recursion without memoization often fail or become inefficient for problems like Fibonacci sequence calculation?

A Because recursion uses loops internally which slow down the program

B Because recursion always uses more memory than iteration

C Because recursion repeats the same calculations multiple times leading to exponential time complexity

D Because recursion cannot handle base cases properly

💡 Hint

Think about how many times fib(2) is calculated in fib(5) without memoization.

Simple recursion recalculates the same subproblems many times, causing exponential growth in calls and slowing down the program drastically.

❓ Predict Output

advanced

Output of Bottom-Up Dynamic Programming Fibonacci

What is the output of this C code that calculates Fibonacci numbers using bottom-up dynamic programming?

DSA C

#include <stdio.h>

int fib(int n) {
    int dp[100] = {0};
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    printf("%d\n", fib(7));
    return 0;
}

A 21

B 34

C 55

D 13

💡 Hint

Recall the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...

fib(7) returns the 7th Fibonacci number starting from fib(0)=0, which is 13.

🧠 Conceptual

expert

When to Prefer Dynamic Programming Over Recursion

In which scenario is dynamic programming preferred over simple recursion?

A When the problem can be solved only by iteration

B When the problem has no repeated calculations

C When recursion depth is always less than 10

D When the problem has overlapping subproblems and optimal substructure

💡 Hint

Think about problems where subproblems repeat and results can be reused.

Dynamic programming is best when problems have overlapping subproblems and optimal substructure, allowing reuse of results to improve efficiency.