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.

Practice

1. What is the main purpose of using memoization in recursive functions?

easy

A. To avoid using any variables inside the function

B. To make the function run slower by adding extra steps

C. To convert recursion into iteration automatically

D. To store results of expensive function calls and reuse them later

Solution

1. Step 1: Understand recursion inefficiency

   Recursive functions often repeat the same calculations multiple times, which wastes time.

2. Step 2: Role of memoization

   Memoization saves the results of these repeated calculations in a storage (like an object) so they can be reused without recalculating.

3. Final Answer:

   To store results of expensive function calls and reuse them later -> Option D

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated results to speed up recursion [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with iteration
• Believing memoization removes recursion

2. Which of the following is the correct way to declare a memo object in TypeScript for memoization?

easy

A. let memo = []

B. const memo: Record = {}

C. var memo = 0

D. const memo: string = ''

Solution

1. Step 1: Identify memo storage type

   Memoization requires a storage that maps input (number) to output (number), so an object with number keys and number values is suitable.

2. Step 2: Check TypeScript syntax

   Record correctly types an object with number keys and number values.

3. Final Answer:

   const memo: Record = {} -> Option B

4. Quick Check:

   Memo object type = Record [OK]

Hint: Use Record for memo object in TypeScript [OK]

Common Mistakes:

• Using array instead of object for memo
• Declaring memo as a number or string
• Not initializing memo as an empty object

3. What will be the output of the following TypeScript code?

function fib(n: number, memo: Record = {}): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci sequence

   Fibonacci numbers start as 0,1,1,2,3,5,8,... The 5th Fibonacci number (0-based) is 5.

2. Step 2: Trace fib(5) call

   fib(5) = fib(4) + fib(3) = 3 + 2 = 5, memoization avoids repeated calls.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember Fibonacci sequence values for small n [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Ignoring memoization effect on output
• Calculating fib(5) as fib(6)

4. Identify the error in this memoized factorial function and choose the correct fix:

function factorial(n: number, memo: Record = {}): number {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1, memo);
  return memo[n];
}
console.log(factorial(5));

medium

A. Remove memo parameter from function

B. Add base case for n === 1

C. Change if (memo[n]) to if (memo[n] !== undefined)

D. Initialize memo as an array instead of object

Solution

1. Step 1: Understand memo check issue

   Checking if (memo[n]) fails when memo[n] is 0 or falsy, but factorial values are always positive, so 0 is not possible here, but better to check for undefined explicitly.

2. Step 2: Fix condition to check existence properly

   Use if (memo[n] !== undefined) to correctly detect cached values.

3. Final Answer:

   Change if (memo[n]) to if (memo[n] !== undefined) -> Option C

4. Quick Check:

   Check memo existence with !== undefined [OK]

Hint: Check memo keys with !== undefined to avoid false negatives [OK]

Common Mistakes:

• Using if(memo[n]) which fails for falsy cached values
• Adding unnecessary base case for n=1
• Removing memo parameter breaks memoization

5. You want to optimize a recursive function that calculates the number of ways to climb n stairs taking 1 or 2 steps at a time. Which memoization approach below correctly implements this in TypeScript?

hard

A. function climb(n: number, memo: Record = {}): number {
if (n <= 1) return 1;
if (memo[n] !== undefined) return memo[n];
memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
return memo[n];
}

B. function climb(n: number): number {
if (n <= 1) return 1;
return climb(n - 1) + climb(n - 2);
}

C. function climb(n: number, memo: number[] = []): number {
if (n <= 1) return 1;
if (memo[n]) return memo[n];
memo[n] = climb(n - 1, memo) * climb(n - 2, memo);
return memo[n];
}

D. function climb(n: number, memo: Record = {}): number {
if (n === 0) return 0;
if (memo[n]) return memo[n];
memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
return memo[n];
}

Solution

1. Step 1: Understand problem base cases

   Number of ways to climb 0 or 1 stairs is 1 (one way: stand still or one step).

2. Step 2: Check memoization and recursion logic

   function climb(n: number, memo: Record = {}): number { if (n <= 1) return 1; if (memo[n] !== undefined) return memo[n]; memo[n] = climb(n - 1, memo) + climb(n - 2, memo); return memo[n]; } correctly uses memo object, checks with !== undefined, and sums ways from n-1 and n-2 stairs.

3. Step 3: Identify errors in other options

   function climb(n: number): number { if (n <= 1) return 1; return climb(n - 1) + climb(n - 2); } lacks memoization, function climb(n: number, memo: number[] = []): number { if (n <= 1) return 1; if (memo[n]) return memo[n]; memo[n] = climb(n - 1, memo) * climb(n - 2, memo); return memo[n]; } multiplies instead of sums, function climb(n: number, memo: Record = {}): number { if (n === 0) return 0; if (memo[n]) return memo[n]; memo[n] = climb(n - 1, memo) + climb(n - 2, memo); return memo[n]; } returns 0 for n=0 which is incorrect.

4. Final Answer:

   Option A code correctly implements memoized climb function -> Option A

5. Quick Check:

   Memo + sum of previous two = correct climb ways [OK]

Hint: Sum ways for n-1 and n-2 with memo check !== undefined [OK]

Common Mistakes:

• Forgetting memoization causing slow recursion
• Multiplying instead of adding ways
• Wrong base case for n=0