Memoization to Optimize Recursion in DSA Typescript - Build from Scratch

Memoization to Optimize Recursion

📖 Scenario: Imagine you want to calculate the number of ways to climb a staircase with a certain number of steps. You can climb either 1 or 2 steps at a time. This is a classic problem where recursion can be slow because it repeats the same calculations many times.Memoization helps by remembering the results of previous calculations so you don't repeat work.

🎯 Goal: You will build a recursive function to calculate the number of ways to climb stairs, then optimize it using memoization to make it faster.

📋 What You'll Learn

Create a recursive function to calculate ways to climb stairs

Add a memo object to store results of previous calculations

Modify the recursive function to use the memo object

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world problems like calculating Fibonacci numbers, optimizing game moves, and speeding up complex calculations.

💼 Career

Understanding memoization helps in writing efficient code, which is important for software engineers, data scientists, and anyone working with algorithms.

1

Create a recursive function to calculate ways to climb stairs

Create a function called countWays that takes a number n and returns the number of ways to climb n steps. Use recursion with these rules:
- If n is 0 or 1, return 1.
- Otherwise, return countWays(n - 1) + countWays(n - 2).

DSA Typescript

// Your code here

Hint

Think of the base cases first: when n is 0 or 1, there is only 1 way to climb.

For other cases, add the ways to climb (n-1) and (n-2) steps.

2

Add a memo object to store previous results

Create a variable called memo as an empty object {} to store results of previous calculations.

DSA Typescript

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

// Your code here

Hint

This object will hold numbers as keys and their calculated ways as values.

3

Modify the recursive function to use the memo object

Update the countWays function to use the memo object:
- Before calculating, check if memo[n] exists and return it if yes.
- After calculating the result, store it in memo[n] before returning.

DSA Typescript

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

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

Hint

Check if the answer is already in memo. If yes, return it to avoid repeated work.

If not, calculate and save it in memo.

4

Print the number of ways to climb 5 steps

Write a console.log statement to print the result 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

Use console.log(countWays(5)) to see the number of ways to climb 5 steps.