Memoization to Optimize Recursion in DSA Javascript

Mental Model

Memoization remembers answers to problems we've solved before so we don't repeat work.

Analogy: It's like writing down answers in a notebook when you solve a puzzle, so next time you see the same puzzle, you just look it up instead of solving it again.

call fib(4)
  ↓
fib(4) -> fib(3) + fib(2)
  ↓           ↓
fib(3) -> fib(2) + fib(1)   fib(2)
  ↓           ↓
fib(2) -> fib(1) + fib(0)
  ↓
fib(1) and fib(0) are base cases

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Find fib(5) efficiently by storing results of fib(2), fib(3), etc. to avoid repeated work

Step 1: Call fib(5), no memo entry yet

memo = {}
fib(5) calls fib(4) and fib(3)

Why: We start by breaking fib(5) into smaller problems fib(4) and fib(3)

Step 2: Call fib(4), no memo entry yet

memo = {}
fib(4) calls fib(3) and fib(2)

Why: We break fib(4) further to solve smaller parts

Step 3: Call fib(3), no memo entry yet

memo = {}
fib(3) calls fib(2) and fib(1)

Why: Keep breaking down until base cases

Step 4: Call fib(2), no memo entry yet

memo = {}
fib(2) calls fib(1) and fib(0)

Why: Reach base cases fib(1)=1 and fib(0)=0

Step 5: fib(1) and fib(0) return 1 and 0, fib(2) = 1 + 0 = 1, store memo[2] = 1

memo = {2:1}

Why: Store fib(2) result to reuse later

Step 6: fib(1) returns 1, fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store memo[3] = 2

memo = {2:1, 3:2}

Why: Store fib(3) result to avoid recomputing

Step 7: fib(2) found in memo as 1, fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store memo[4] = 3

memo = {2:1, 3:2, 4:3}

Why: Reuse memoized fib(2) to save time

Step 8: fib(3) found in memo as 2, fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store memo[5] = 5

memo = {2:1, 3:2, 4:3, 5:5}

Why: Final answer fib(5) computed using memoized results

Result:

memo = {2:1, 3:2, 4:3, 5:5}
fib(5) = 5

Annotated Code

DSA Javascript

class Fibonacci {
  constructor() {
    this.memo = {};
  }

  fib(n) {
    if (n <= 1) return n; // base case
    if (this.memo[n] !== undefined) return this.memo[n]; // return cached result

    // compute fib(n-1) and fib(n-2) recursively
    const result = this.fib(n - 1) + this.fib(n - 2);
    this.memo[n] = result; // store result in memo
    return result;
  }
}

const fibCalc = new Fibonacci();
console.log(fibCalc.fib(5));

if (n <= 1) return n; // base case

return base case values 0 or 1 to stop recursion

if (this.memo[n] !== undefined) return this.memo[n]; // return cached result

check if result already computed to avoid repeated work

const result = this.fib(n - 1) + this.fib(n - 2);

recursively compute fib(n) from smaller subproblems

this.memo[n] = result; // store result in memo

save computed result for future calls

Output

5

Complexity Analysis

Time: O(n) because each fib number from 0 to n is computed once and stored

Space: O(n) for the memo object storing results and recursion call stack

vs Alternative: Without memoization, time is O(2^n) due to repeated calls; memoization reduces it to linear time

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Javascript

if (n <= 1) return n; // base case

n = 1

Returns 1 immediately as base case

DSA Javascript

if (n <= 1) return n; // base case

Repeated calls with same n

Returns cached result from memo without recomputing

DSA Javascript

if (this.memo[n] !== undefined) return this.memo[n]; // return cached result

When to Use This Pattern

When you see a recursive problem with overlapping subproblems, reach for memoization to save repeated work and speed up the solution.

Common Mistakes

Mistake: Not storing the computed result in the memo object after recursion
Fix: Add memo[n] = result after computing fib(n) to save it for future calls

Mistake: Not checking the memo before recursive calls, causing repeated work
Fix: Check if memo[n] exists before recursion and return it immediately if found

Summary

Memoization saves results of recursive calls to avoid repeating the same work.

Use it when recursion solves the same subproblems multiple times.

Remember: store results after computing and check before computing.

Practice

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

easy

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

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

C. To avoid using recursion altogether

D. To increase the number of recursive calls

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so that if the same inputs occur again, the saved result is used instead of recalculating.

2. Step 2: Identify the effect on recursion

   This reduces repeated work and speeds up recursive functions by avoiding duplicate calculations.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated work to speed recursion [OK]

Common Mistakes:

• Thinking memoization makes recursion slower
• Confusing memoization with iteration
• Believing memoization removes recursion

2. Which of the following is the correct way to declare a memo object inside a recursive function in JavaScript?

easy

A. const memo = {}; inside the function, then pass it as a parameter

B. var memo = []; inside the function without passing it

C. let memo = 0; inside the function

D. memo = new Map(); outside the function and never pass it

Solution

1. Step 1: Understand memo object usage

   The memo object should be an object or map to store key-value pairs of inputs and results.

2. Step 2: Correct placement and passing

   Declaring const memo = {} inside the function and passing it as a parameter ensures the same memo is used across recursive calls.

3. Final Answer:

   const memo = {}; inside the function, then pass it as a parameter -> Option A

4. Quick Check:

   Memo object declared and passed = const memo = {}; inside the function, then pass it as a parameter [OK]

Hint: Declare memo as object and pass it to recursive calls [OK]

Common Mistakes:

• Using array instead of object for memo
• Not passing memo to recursive calls
• Declaring memo as a number

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

function fib(n, memo = {}) {
  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. Undefined

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   fib(5) calculates Fibonacci number at position 5 using memo to avoid repeated calls.

2. Step 2: Calculate fib(5) step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memo and recalculating
• Assuming output is 8

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

function factorial(n, memo = {}) {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1);
  return memo[n];
}

medium

A. Remove memo object completely

B. Change base case to n === 1

C. Pass memo in recursive call: factorial(n - 1, memo)

D. Initialize memo as an array instead of object

Solution

1. Step 1: Check recursive call parameters

   The recursive call to factorial misses passing the memo object, so memo is reset each time.

2. Step 2: Fix by passing memo in recursion

   Change call to factorial(n - 1, memo) to keep memo consistent across calls.

3. Final Answer:

   Pass memo in recursive call: factorial(n - 1, memo) -> Option C

4. Quick Check:

   Pass memo to recursive calls to fix [OK]

Hint: Always pass memo object in recursive calls [OK]

Common Mistakes:

• Forgetting to pass memo in recursion
• Changing base case unnecessarily
• Removing memo defeats optimization

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 improves performance?

hard

A. Store results only for even stair numbers in memo

B. Use a global variable to count calls without storing results

C. Rewrite the function to use a loop without memoization

D. Use a memo object passed through recursive calls to store results for each stair number

Solution

1. Step 1: Understand the problem and recursion

   The function counts ways to climb stairs by summing ways(n-1) and ways(n-2).

2. Step 2: Apply memoization correctly

   Passing a memo object through recursive calls stores results for each stair number, avoiding repeated calculations.

3. Step 3: Evaluate other options

   Global counters don't store results, loops change approach, and storing only even results misses odd cases.

4. Final Answer:

   Use a memo object passed through recursive calls to store results for each stair number -> Option D

5. Quick Check:

   Memo object for all inputs optimizes recursion [OK]

Hint: Memoize all inputs to avoid repeated stair count calculations [OK]

Common Mistakes:

• Not passing memo object through recursion
• Partial memoization missing some inputs
• Confusing memoization with iteration