Memoization to Optimize Recursion in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following TypeScript code that calculates Fibonacci numbers using memoization?

DSA Typescript

function fib(n: number, memo: Record<number, number> = {}): 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(6));

A 5

B 13

C 8

D 21

💡 Hint

Remember Fibonacci sequence starts 0,1,1,2,3,5,8,13...

The Fibonacci sequence (0-indexed): fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8. The code returns 8.

❓ Predict Output

intermediate

Memoization Cache Content After Execution

After running the following code, what is the content of the memo object?

DSA Typescript

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

A {"4":24}

B {"2":2,"3":6,"4":24}

C {"3":6,"4":24}

D {"1":1,"2":2,"3":6,"4":24}

💡 Hint

Factorial builds up from 1 to n, memo stores intermediate results.

The memo stores factorial results for 2, 3, and 4. It does not store 1 because base case returns 1 without memoizing.

🔧 Debug

advanced

Identify the Error in Memoized Fibonacci

What error will this TypeScript code produce when run?

DSA Typescript

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

A Output: 5

B Stack overflow due to infinite recursion

C TypeError: Cannot read property '5' of undefined

D Output: 8

💡 Hint

Check how memo is passed in recursive calls.

No TypeError occurs because the default parameter provides a new {} memo when omitted. The code outputs 5 correctly, but memo is not shared between fib(n-1) and fib(n-2) branches, causing redundant calculations.

❓ Predict Output

advanced

Output of Memoized Climbing Stairs Problem

What is the output of this memoized climbing stairs function for n=4?

DSA Typescript

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

A 3

B 7

C 6

D 5

💡 Hint

Number of ways to climb 4 steps taking 1 or 2 steps at a time.

Ways to climb 4 steps: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 = 5 ways.

🧠 Conceptual

expert

Why Memoization Improves Recursive Fibonacci

Which statement best explains why memoization improves the performance of the recursive Fibonacci function?

A It stores previously computed results to avoid repeated calculations, reducing exponential time to linear time.

B It changes the recursion to iteration, which is faster in all cases.

C It parallelizes the recursive calls to run simultaneously on multiple processors.

D It uses a stack data structure to store all recursive calls explicitly.

💡 Hint

Think about how many times each Fibonacci number is calculated without memoization.

Memoization caches results so each Fibonacci number is calculated once, reducing time complexity from exponential to linear.