Why Dynamic Programming and When Recursion Alone Fails in DSA C++ - See It Work

Why Dynamic Programming and When Recursion Alone Fails

📖 Scenario: Imagine you want to find the number of ways to climb a staircase with 5 steps. You can take either 1 step or 2 steps at a time. This is a common problem where recursion alone can be slow because it repeats the same calculations many times.We will explore how simple recursion works and why it can be inefficient. Then, we will see how dynamic programming helps by remembering past results to avoid repeated work.

🎯 Goal: Build a simple program that first uses recursion to count ways to climb stairs, then add a memory (cache) to store results and speed up the process. You will see why recursion alone fails and how dynamic programming fixes it.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Add a cache (array) to store intermediate results

Modify the recursive function to use the cache

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Counting ways to climb stairs models many real-world problems like counting paths, combinations, and sequences where choices build on previous results.

💼 Career

Understanding why recursion alone can be inefficient and how dynamic programming optimizes it is key for software engineers solving optimization and algorithmic problems.

1

Create a recursive function to count ways to climb stairs

Write a recursive function called countWays that takes an integer n and returns the number of ways to climb n steps. Use the base cases: if n == 0 or n == 1, return 1. For other cases, return countWays(n - 1) + countWays(n - 2). Also, in main(), call countWays(5) and store the result in an integer variable called result.

DSA C++

#include 
using namespace std;

int countWays(int n) {
    // Write the recursive function here
    // Your code here
}

int main() {
    // Call countWays(5) and store in result
    // Your code here
    return 0;
}

Hint

Think of the problem like climbing stairs: from step n, you can come from n-1 or n-2 steps. Use this idea in your recursion.

2

Add a cache array to store intermediate results

Create a global integer array called cache of size 6 (to store results for steps 0 to 5). Initialize all elements to -1 to indicate uncalculated values.

DSA C++

#include 
using namespace std;

int cache[6]; // Create cache array

int countWays(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return countWays(n - 1) + countWays(n - 2);
}

int main() {
    // Initialize cache elements to -1
    // Your code here
    int result = countWays(5);
    return 0;
}

Hint

Use a for loop to set each element of cache to -1.

3

Modify the recursive function to use the cache

Change the countWays function to first check if cache[n] is not -1. If so, return cache[n]. Otherwise, compute the value recursively, store it in cache[n], and then return it.

DSA C++

#include 
using namespace std;

int cache[6];

int countWays(int n) {
    // Check cache first
    // Your code here
    if (n == 0 || n == 1) {
        return 1;
    }
    // Compute and store in cache
    // Your code here
}

int main() {
    for (int i = 0; i < 6; i++) {
        cache[i] = -1;
    }
    int result = countWays(5);
    return 0;
}

Hint

Use the cache to avoid repeating calculations. If the value is already in cache[n], return it immediately.

4

Print the number of ways to climb 5 steps

Add a cout statement in main() to print the value of result.

DSA C++

#include 
using namespace std;

int cache[6];

int countWays(int n) {
    if (cache[n] != -1) {
        return cache[n];
    }
    if (n == 0 || n == 1) {
        cache[n] = 1;
        return 1;
    }
    cache[n] = countWays(n - 1) + countWays(n - 2);
    return cache[n];
}

int main() {
    for (int i = 0; i < 6; i++) {
        cache[i] = -1;
    }
    int result = countWays(5);
    // Print the result
    // Your code here
    return 0;
}

Hint

Use cout << result << endl; to display the number of ways.

Practice

1. Why do we use dynamic programming instead of plain recursion for some problems?

easy

A. Because dynamic programming stores results to avoid repeated work

B. Because recursion is always slower than loops

C. Because recursion cannot solve problems with multiple choices

D. Because dynamic programming uses less memory than recursion

Solution

1. Step 1: Understand recursion's limitation

   Recursion often recalculates the same subproblems multiple times, causing inefficiency.

2. Step 2: Role of dynamic programming

   Dynamic programming saves results of subproblems to reuse them, avoiding repeated calculations.

3. Final Answer:

   Because dynamic programming stores results to avoid repeated work -> Option A

4. Quick Check:

   Memoization avoids repeated work = A [OK]

Hint: Dynamic programming saves sub-results to speed up recursion [OK]

Common Mistakes:

• Thinking recursion is always slower than loops
• Believing recursion can't handle multiple choices
• Assuming dynamic programming uses less memory always

2. Which of the following is the correct syntax to declare a memoization array for a Fibonacci function in C++?

easy

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

B. int memo(100, -1);

C. vector<int> memo(100, -1);

D. int memo[] = new int[100];

Solution

1. Step 1: Identify correct C++ container for memoization

   Using vector<int> memo(100, -1); initializes a vector of size 100 with all values -1, suitable for memoization.

2. Step 2: Check other options

   int memo[100] = {0}; initializes array with zeros, not -1 (commonly used to mark unvisited). int memo(100, -1); uses wrong syntax for array. int memo[] = new int[100]; uses incorrect syntax for dynamic array in C++.

3. Final Answer:

   vector<int> memo(100, -1); -> Option C

4. Quick Check:

   Vector with size and initial value = D [OK]

Hint: Use vector<int> with size and -1 for memo arrays [OK]

Common Mistakes:

• Using C-style arrays without initialization
• Confusing array and vector syntax
• Initializing memo with zeros instead of -1

3. What is the output of the following C++ code snippet?

int fib(int n, vector<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() {
  vector<int> memo(6, -1);
  cout << fib(5, memo);
  return 0;
}

medium

A. 8

B. Runtime error

C. 13

D. 5

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   fib(5) calculates Fibonacci number at position 5: 0,1,1,2,3,5...

2. Step 2: Trace fib(5) call

   fib(5) = fib(4) + fib(3) = 3 + 2 = 5, memo stores intermediate results to avoid repeats.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   fib(5) = 5 with memoization [OK]

Hint: Fibonacci(5) = 5, memo avoids repeated calls [OK]

Common Mistakes:

• Confusing Fibonacci index starting at 0 or 1
• Expecting fib(5) to be 8 or 13
• Ignoring memo initialization

4. Identify the bug in this recursive Fibonacci function without memoization:

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

int main() {
  cout << fib(50);
  return 0;
}

medium

A. Returns wrong Fibonacci number

B. Stack overflow due to deep recursion

C. Syntax error in function definition

D. No bug, works fine

Solution

1. Step 1: Analyze recursion depth for fib(50)

   fib(50) calls fib(49) and fib(48), which further call many functions, causing very deep recursion.

2. Step 2: Consequence of deep recursion without memoization

   Repeated calls cause exponential time and likely stack overflow error due to too many recursive calls.

3. Final Answer:

   Stack overflow due to deep recursion -> Option B

4. Quick Check:

   Deep recursion without memo causes stack overflow [OK]

Hint: Large n without memo causes stack overflow [OK]

Common Mistakes:

• Thinking syntax error exists
• Assuming function returns wrong value
• Believing no bug exists

5. You want to find the minimum number of coins to make a sum using coins of denominations 1, 3, and 5. Why is recursion alone inefficient here, and how does dynamic programming help?

hard

A. Recursion alone repeats subproblems; dynamic programming stores results to reuse them

B. Recursion cannot handle multiple coin types; dynamic programming can

C. Recursion uses loops internally; dynamic programming uses recursion

D. Recursion always uses more memory than dynamic programming

Solution

1. Step 1: Understand recursion inefficiency in coin change

   Recursion tries all combinations repeatedly, recalculating same sums multiple times.

2. Step 2: How dynamic programming improves efficiency

   Dynamic programming saves results of sub-sums, so each is computed once and reused.

3. Final Answer:

   Recursion alone repeats subproblems; dynamic programming stores results to reuse them -> Option A

4. Quick Check:

   Memoization avoids repeated subproblems = A [OK]

Hint: Store sub-results to avoid repeated calculations [OK]

Common Mistakes:

• Thinking recursion can't handle multiple coin types
• Confusing recursion and loops
• Assuming recursion always uses more memory