DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Visual Comparison

Concept Flow - DP vs Recursion vs Greedy Choosing the Right Tool

Start Problem

↓

Is problem optimal substructure?

↓

Is problem overlapping subproblems?

↓

Use DP (Memoization or Tabulation)

↓

Can greedy choice property be applied?

↓

Use Greedy Algorithm

↓

Solve Problem Efficiently

↓

End

This flow shows how to decide between DP, recursion, and greedy by checking problem properties step-by-step.

Execution Sample

DSA Typescript

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

Simple recursive Fibonacci function showing overlapping subproblems and exponential calls.

Execution Table

Step	Call Stack	Current Call	Action	Result/Return	Notes
1	fib(4)	fib(4)	Calls fib(3) and fib(2)	Pending	Start with fib(4)
2	fib(4) -> fib(3)	fib(3)	Calls fib(2) and fib(1)	Pending	fib(3) needs fib(2) and fib(1)
3	fib(4) -> fib(3) -> fib(2)	fib(2)	Calls fib(1) and fib(0)	Pending	fib(2) calls base cases
4	fib(4) -> fib(3) -> fib(2) -> fib(1)	fib(1)	Base case returns 1	1	fib(1) = 1
5	fib(4) -> fib(3) -> fib(2) -> fib(0)	fib(0)	Base case returns 0	0	fib(0) = 0
6	fib(4) -> fib(3) -> fib(2)	fib(2)	Returns fib(1)+fib(0)	1	fib(2) = 1 + 0 = 1
7	fib(4) -> fib(3) -> fib(1)	fib(1)	Base case returns 1	1	fib(1) = 1
8	fib(4) -> fib(3)	fib(3)	Returns fib(2)+fib(1)	2	fib(3) = 1 + 1 = 2
9	fib(4) -> fib(2)	fib(2)	Calls fib(1) and fib(0) again	Pending	Repeated calls show overlapping subproblems
10	fib(4) -> fib(2) -> fib(1)	fib(1)	Base case returns 1	1	fib(1) = 1
11	fib(4) -> fib(2) -> fib(0)	fib(0)	Base case returns 0	0	fib(0) = 0
12	fib(4) -> fib(2)	fib(2)	Returns fib(1)+fib(0)	1	fib(2) = 1 + 0 = 1
13	fib(4)	fib(4)	Returns fib(3)+fib(2)	3	fib(4) = 2 + 1 = 3
14	-	-	-	-	All calls resolved, recursion ends

💡 All recursive calls completed, final result fib(4) = 3

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	Final
Call Stack Depth	1	4	3	2	2	0
fib(1) Result	N/A	1	1	1	1	1
fib(0) Result	N/A	0	0	0	0	0
fib(2) Result	N/A	Pending	1	1	1	1
fib(3) Result	N/A	Pending	Pending	2	2	2
fib(4) Result	N/A	Pending	Pending	Pending	Pending	3

Key Moments - 3 Insights

Why does fib(2) get called multiple times in the recursion?

Because the recursion does not remember previous results, fib(2) is recomputed each time it is needed, as shown in steps 3 and 9 in the execution_table.

When should we choose a greedy algorithm over DP or recursion?

Choose greedy only if the problem has the greedy choice property and optimal substructure, meaning local optimal choices lead to global optimum. Otherwise, DP or recursion is safer.

How does DP improve over plain recursion?

DP stores results of subproblems (memoization or tabulation) to avoid repeated work, unlike recursion which recomputes, as seen by repeated calls in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result returned by fib(3) at step 8?

A 3

B 1

C 2

D Pending

💡 Hint

Check the 'Result/Return' column at step 8 in the execution_table.

At which step does the recursion start to return base case values?

A Step 1

B Step 4

C Step 9

D Step 13

💡 Hint

Look for 'Base case returns' in the 'Action' column in execution_table.

If we use DP (memoization), how would the execution_table change?

A Fewer repeated calls like fib(2), reducing steps

B More base case calls

C More calls to fib(0)

D No change in call stack depth

💡 Hint

Refer to repeated fib(2) calls at steps 3 and 9 in execution_table.

Concept Snapshot

DP vs Recursion vs Greedy Quick Guide:
- Recursion: simple, solves by calling itself, but may repeat work
- DP: recursion + memoization/tabulation to avoid repeats
- Greedy: picks best local choice, fast if problem fits
- Choose DP if overlapping subproblems + optimal substructure
- Choose Greedy if greedy choice property holds
- Otherwise, use plain recursion for simple or small problems

Full Transcript

This lesson shows how to choose between dynamic programming, recursion, and greedy algorithms by checking problem properties. Recursion solves problems by calling itself but can repeat work, as seen in the Fibonacci example where fib(2) is called multiple times. Dynamic programming improves recursion by storing results to avoid repeats. Greedy algorithms pick the best local choice and work well if the problem has the greedy choice property. The execution table traces recursive calls for fib(4), showing call stack growth and returns. Key moments clarify why repeated calls happen and when to pick each approach. The visual quiz tests understanding of recursion steps and DP benefits.

Practice

1. Which approach is best when a problem can be broken into overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand overlapping subproblems

   Dynamic Programming works well when subproblems repeat and can be reused.

2. Step 2: Check optimal substructure property

   Dynamic Programming uses optimal solutions of subproblems to build the final solution.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memoization causing slow code
• Confusing brute force with DP

2. Which of the following TypeScript function signatures correctly implements a recursive Fibonacci function?

easy

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

B. function fib(n: number): number { let a = 0; let b = 1; for(let i=2; i<=n; i++) { let c = a + b; a = b; b = c; } return b; }

C. function fib(n: number): number { return n + fib(n-1); }

D. function fib(n: number): number { if(n == 0) return 0; else return fib(n-1) * fib(n-2); }

Solution

1. Step 1: Check base case correctness

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } returns n if n <= 1, which correctly handles fib(0)=0 and fib(1)=1.

2. Step 2: Check recursive calls

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } calls fib(n-1) + fib(n-2), matching Fibonacci definition.

3. Final Answer:

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } -> Option A

4. Quick Check:

   Correct base case and recursive sum = function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } [OK]

Hint: Base case n<=1 and sum of fib(n-1)+fib(n-2) is key [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using multiplication instead of addition
• Incorrect loop instead of recursion

3. What is the output of the following TypeScript code using recursion to calculate factorial?

function factorial(n: number): number {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 10

B. Error

C. 120

D. 24

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3), factorial(3) = 3 * factorial(2), factorial(2) = 2 * factorial(1), factorial(1) = 1 * factorial(0), factorial(0) = 1.

2. Step 2: Calculate values bottom-up

   factorial(0) = 1, factorial(1) = 1*1=1, factorial(2) = 2*1=2, factorial(3) = 3*2=6, factorial(4) = 4*6=24.

3. Final Answer:

   24 -> Option D

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n*(n-1)! with base 0! = 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Missing base case causing stack overflow
• Incorrect multiplication order

4. The following greedy algorithm tries to find the minimum number of coins for a given amount. What is the bug?

function minCoins(coins: number[], amount: number): number {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (let coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
console.log(minCoins([1, 3, 4], 6));

medium

A. Sorting coins ascending instead of descending

B. Greedy fails for coin sets where local choice isn't optimal

C. Using floor division instead of ceil

D. Not handling zero amount input

Solution

1. Step 1: Understand greedy approach for coin change

   Greedy picks largest coin first, but it may not yield minimum coins for all coin sets.

2. Step 2: Check example with coins [1,3,4] and amount 6

   Greedy picks 4 once, then 1 twice = 3 coins; but optimal is 3+3 = 2 coins.

3. Final Answer:

   Greedy fails for coin sets where local choice isn't optimal -> Option B

4. Quick Check:

   Greedy not always optimal for coin change [OK]

Hint: Greedy fails if local best choice isn't globally best [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring coin sorting order
• Confusing floor and ceil division

5. You want to find the longest increasing subsequence (LIS) in an array. Which approach is best and why?
const arr = [10, 9, 2, 5, 3, 7, 101, 18];

hard

A. Greedy, because picking local max always gives LIS

B. Recursion without memoization, to explore all subsequences

C. Dynamic Programming, to store LIS lengths and build solution efficiently

D. Brute force, checking all subsequences

Solution

1. Step 1: Analyze problem characteristics

   LIS requires checking many subsequences with overlapping subproblems and optimal substructure.

2. Step 2: Choose approach with efficiency

   Dynamic Programming stores LIS lengths for subproblems, avoiding repeated work and improving speed.

3. Final Answer:

   Dynamic Programming, to store LIS lengths and build solution efficiently -> Option C

4. Quick Check:

   LIS best solved by DP due to overlapping subproblems [OK]

Hint: Use DP for LIS to avoid exponential recursion [OK]

Common Mistakes:

• Using greedy which fails for LIS
• Recursion without memoization causing slow code
• Trying brute force which is inefficient