Why Dynamic Programming and When Recursion Alone Fails in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Without Memoization

What is the output of the following TypeScript code that calculates Fibonacci numbers using simple recursion without any optimization?

DSA Typescript

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

console.log(fib(5));

A 5

B 8

C 13

D 3

💡 Hint

Remember that fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2).

The function calculates Fibonacci numbers recursively. fib(5) = fib(4) + fib(3) = 3 + 2 = 5.

🧠 Conceptual

intermediate

Why Recursion Alone Can Be Inefficient

Which of the following best explains why simple recursion can be inefficient for problems like Fibonacci sequence calculation?

A It recalculates the same subproblems multiple times, causing exponential time complexity.

B It uses too much memory because it stores all results in a table.

C It cannot handle base cases properly, leading to infinite loops.

D It always requires iterative loops to work correctly.

💡 Hint

Think about how many times fib(2) is calculated in fib(5).

Simple recursion recalculates the same subproblems many times, which leads to exponential time complexity and inefficiency.

❓ Predict Output

advanced

Output of Fibonacci with Memoization

What is the output of this TypeScript code that uses memoization to optimize Fibonacci calculation?

DSA Typescript

function fibMemo(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(10));

A 89

B 55

C 34

D 144

💡 Hint

Recall the Fibonacci sequence: 0,1,1,2,3,5,8,13,21,34,55,...

fibMemo(10) returns the 10th Fibonacci number which is 55. Memoization avoids repeated calculations.

🧠 Conceptual

advanced

When to Use Dynamic Programming Instead of Recursion

Which scenario best describes when dynamic programming is preferred over simple recursion?

A When the problem cannot be broken down into smaller subproblems.

B When the problem requires only a single recursive call per step.

C When the problem has overlapping subproblems and optimal substructure, making recursion inefficient.

D When the problem has no repeated calculations and recursion is already fast.

💡 Hint

Think about problems where the same smaller problems appear multiple times.

Dynamic programming is best when problems have overlapping subproblems and optimal substructure, allowing reuse of results to improve efficiency.

🔧 Debug

expert

Identify the Error in Recursive Fibonacci with Memoization

What error does the following TypeScript code produce when calling fibMemo(5)?

DSA Typescript

function fibMemo(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(5));

A Causes a stack overflow error

B Returns 5 correctly without error

C Throws a TypeError because memo is undefined

D Returns undefined due to incorrect memo check

💡 Hint

Check how the memo object is checked before returning stored values.

The condition 'if (memo[n])' fails when memo[n] is 0, which is falsy, causing repeated calls and incorrect behavior.