Why Dynamic Programming and When Recursion Alone Fails in DSA Typescript - 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 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 learn how to use dynamic programming to avoid repeating work and make the solution faster.

🎯 Goal: Build a simple program that first uses recursion to count ways to climb stairs, then improves it using dynamic programming with memoization to avoid repeated calculations.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Add a memo object to store results of subproblems

Modify the recursive function to use the memo object

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Counting ways to do tasks with overlapping steps appears in many real-world problems like route planning, resource allocation, and game moves.

💼 Career

Understanding when recursion is inefficient and how dynamic programming optimizes it is key for software engineers solving complex algorithm problems.

1

Create a recursive function to count ways to climb stairs

Create a function called countWays that takes a number n representing steps left. If n is 0 or 1, return 1. Otherwise, return the sum of countWays(n - 1) and countWays(n - 2). Then call countWays(5) and store the result in a variable called result.

DSA Typescript

// Your code here

Hint

Think about the base cases for 0 and 1 steps. Then use recursion to add the ways for smaller steps.

2

Add a memo object to store results of subproblems

Create an empty object called memo to store previously calculated results for each n.

DSA Typescript

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

const memo: {[key: number]: number} = {};
// Your code here

Hint

This object will help us remember answers for each step count to avoid repeating work.

3

Modify the recursive function to use the memo object

Change the countWays function to first check if n is in memo. If yes, return memo[n]. Otherwise, calculate the result recursively, store it in memo[n], and then return it.

DSA Typescript

function countWays(n: number): number {
    if (n === 0 || n === 1) {
        return 1;
    }
    // Your code here
}

const memo: {[key: number]: number} = {};

Hint

Use the memo object to save results and check before computing again.

4

Print the number of ways to climb 5 steps

Add a console.log statement to print the value of countWays(5).

DSA Typescript

const memo: {[key: number]: number} = {};

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

// Your code here

Hint

The output should be the number of ways to climb 5 steps, which is 8.