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 climb 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 recursion works here 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 in C that uses recursion to count ways to climb stairs, then add a helper array to store results (dynamic programming) to make it faster.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Add an array to store intermediate results (memoization)

Modify the recursive function to use the stored results

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Counting ways to climb stairs is like many problems in real life where you combine smaller steps to reach a goal, such as planning routes or breaking tasks into parts.

💼 Career

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

1

Create a recursive function to count ways to climb stairs

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

DSA C

#include 

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

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

Hint

Use the base cases to stop recursion. For other cases, call countWays for n-1 and n-2 and add the results.

2

Add an array to store intermediate results (memoization)

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

DSA C

#include 

int memo[6];

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

int main() {
    int result = countWays(5);
    return 0;
}

Hint

Declare the array outside all functions so it is global. Initialize all elements to -1.

3

Modify the recursive function to use the stored results

Update the countWays function to check if memo[n] is not -1. If so, return memo[n]. Otherwise, calculate the value recursively, store it in memo[n], and then return it.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

int countWays(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    // Check if memo[n] is calculated
    // If yes, return memo[n]
    // Otherwise, calculate and store in memo[n]
    // Your code here
}

int main() {
    int result = countWays(5);
    return 0;
}

Hint

Use the memo array to save results and avoid repeated calculations.

4

Print the number of ways to climb 5 steps

Add a printf statement in main to print the value of result with the message: "Number of ways to climb 5 steps: %d\n".

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

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

int main() {
    int result = countWays(5);
    // Print the result below
    // Your code here
    return 0;
}

Hint

Use printf to show the final answer clearly.