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

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

Start Problem

↓

Check Problem Type

↓

Is problem optimal substructure?

↓

Use Greedy Approach

↓

Is problem overlapping subproblems?

↓

Use Simple Recursion

↓

Use Dynamic Programming

↓

Solve Problem

Decide approach by checking if problem has optimal substructure and overlapping subproblems to choose between greedy, recursion, or dynamic programming.

Execution Sample

DSA Javascript

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

Simple recursion to compute Fibonacci number, showing overlapping subproblems without optimization.

Execution Table

Step	Operation	Call Stack	Subproblem Computed	Result Returned	Notes
1	fib(4) called	fib(4)	No	Pending	Start computation
2	fib(3) called	fib(4), fib(3)	No	Pending	Compute fib(3)
3	fib(2) called	fib(4), fib(3), fib(2)	No	Pending	Compute fib(2)
4	fib(1) called	fib(4), fib(3), fib(2), fib(1)	Yes	1	Base case reached
5	fib(0) called	fib(4), fib(3), fib(2), fib(0)	Yes	0	Base case reached
6	fib(2) returns	fib(4), fib(3)	Yes	1	fib(2) = 1
7	fib(1) called	fib(4), fib(3), fib(1)	Yes	1	Base case reached again
8	fib(3) returns	fib(4)	Yes	2	fib(3) = 2
9	fib(2) called again	fib(4), fib(2)	No	Pending	Repeated subproblem
10	fib(1) called	fib(4), fib(2), fib(1)	Yes	1	Base case
11	fib(0) called	fib(4), fib(2), fib(0)	Yes	0	Base case
12	fib(2) returns	fib(4)	Yes	1	fib(2) = 1 again
13	fib(4) returns		Yes	3	Final result fib(4) = 3
14	End		No	Done	All calls completed

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

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	Final
Call Stack	[]	[fib(4), fib(3), fib(2), fib(1)]	[fib(4), fib(3)]	[fib(4)]	[fib(4)]	[]
fib(1) result	N/A	1	1	1	1	1
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 computed twice in recursion?

Because simple recursion recomputes overlapping subproblems without saving results, as seen in steps 3 and 9 in the execution_table.

When should we use greedy instead of recursion or DP?

Use greedy when the problem has optimal substructure but no overlapping subproblems, so local choices lead to global optimum, as shown in the concept_flow.

How does dynamic programming improve recursion?

DP saves results of subproblems to avoid repeated work, preventing recomputation seen in recursion steps like fib(2) called twice.

Visual Quiz - 3 Questions

Look at the execution_table, what is the call stack just before fib(3) returns?

A [fib(4)]

B [fib(4), fib(3)]

C [fib(4), fib(3), fib(2)]

D []

💡 Hint

Check step 8 in the execution_table for call stack state.

At which step does the recursion detect a repeated subproblem?

A Step 3

B Step 4

C Step 9

D Step 13

💡 Hint

Look for when fib(2) is called again without returning immediately.

If the problem has no overlapping subproblems but has optimal substructure, which approach is best?

A Greedy

B Simple Recursion

C Dynamic Programming

D Brute Force

💡 Hint

Refer to concept_flow where overlapping subproblems decide DP vs Recursion.

Concept Snapshot

DP vs Recursion vs Greedy Quick Guide:
- Check if problem has optimal substructure.
- If no, use Greedy (local best leads to global best).
- If yes, check for overlapping subproblems.
- If overlapping, use Dynamic Programming (memoize results).
- If no overlapping, simple recursion suffices.
- DP avoids repeated work recursion does.

Full Transcript

To choose between Dynamic Programming, Recursion, and Greedy, first check if the problem has optimal substructure, meaning the best solution can be built from best solutions of subproblems. If not, greedy approach works by making local optimal choices. If yes, check if subproblems overlap. If they do, use Dynamic Programming to save results and avoid recomputation. If not, simple recursion is enough. The example of Fibonacci shows recursion recomputing fib(2) twice, which DP would optimize. The execution table traces recursive calls and returns, showing call stack changes and repeated subproblems. Key moments clarify why DP is better for overlapping subproblems and when greedy is suitable. The visual quiz tests understanding of call stack and approach choice.

Practice

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

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand overlapping subproblems and optimal substructure

   Dynamic Programming is designed for problems where subproblems repeat and solutions build on smaller solutions.

2. Step 2: Compare with other approaches

   Greedy algorithms do not always consider overlapping subproblems, recursion without memoization repeats work, and brute force is inefficient.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Look for repeated subproblems and optimal substructure [OK]

Common Mistakes:

• Confusing greedy with DP for overlapping subproblems
• Ignoring memoization in recursion
• Choosing brute force for efficiency

2. Which of the following is the correct syntax to define a recursive function in JavaScript?

easy

A. function factorial(n) { while(n > 0) return n * factorial(n - 1); }

B. function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); }

C. function factorial(n) { for(let i=0; i

D. function factorial(n) { if (n === 0) return 0; return n + factorial(n - 1); }

Solution

1. Step 1: Check base case correctness

   function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } returns 1 when n is 0, which is correct for factorial.

2. Step 2: Check recursive call and return statement

   function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } correctly multiplies n by factorial(n-1). Others have incorrect loops or wrong base cases.

3. Final Answer:

   function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive call = function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } [OK]

Hint: Base case must stop recursion; recursive call must reduce problem size [OK]

Common Mistakes:

• Using loops inside recursion incorrectly
• Wrong base case value
• Returning addition instead of multiplication for factorial

3. What will be the output of the following JavaScript 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. 8

B. 3

C. 5

D. 13

Solution

1. Step 1: Understand the Fibonacci function with memoization

   fib(5) calculates the 5th Fibonacci number using memo to avoid repeated work.

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 C

4. Quick Check:

   fib(5) = 5 with memoization [OK]

Hint: Memoization caches results to speed recursion [OK]

Common Mistakes:

• Confusing Fibonacci index with value
• Ignoring memo object causing slow recursion
• Mixing up base cases

4. Find the error in this greedy algorithm code snippet for coin change problem:

function coinChange(coins, amount) {
  coins.sort();
  let count = 0;
  for (let i = coins.length - 1; i >= 0; i--) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return amount === 0 ? count : -1;
}

medium

A. Return statement should always return count

B. Missing base case for amount = 0

C. Using while loop inside for loop is incorrect

D. coins.sort() sorts ascending, should sort descending

Solution

1. Step 1: Check sorting order for greedy coin change

   Greedy coin change requires coins sorted descending to pick largest first.

2. Step 2: Identify sorting mistake

   coins.sort() sorts ascending by default, so it should be coins.sort((a,b) => b - a).

3. Final Answer:

   coins.sort() sorts ascending, should sort descending -> Option D

4. Quick Check:

   Sort descending for greedy coin change [OK]

Hint: Sort coins descending for greedy coin change [OK]

Common Mistakes:

• Using default ascending sort
• Ignoring sorting affects greedy choice
• Assuming while loop is wrong here

5. You want to find the minimum number of jumps to reach the end of an array where each element represents max jump length at that position. Which approach is best and why?

const arr = [2,3,1,1,4];

hard

A. Greedy, because it chooses the farthest reachable index at each step

B. Recursion without memoization, to explore all paths

C. Dynamic Programming, to store minimum jumps for each index

D. Brute force, to try every possible jump

Solution

1. Step 1: Understand the problem nature

   Minimum jumps problem can be solved efficiently by greedy approach choosing the farthest reachable index.

2. Step 2: Compare approaches

   Recursion without memoization and brute force are inefficient; DP is possible but greedy is optimal and simpler here.

3. Final Answer:

   Greedy, because it chooses the farthest reachable index at each step -> Option A

4. Quick Check:

   Minimum jumps = Greedy approach [OK]

Hint: Pick farthest reachable index greedily for minimum jumps [OK]

Common Mistakes:

• Using recursion without memoization causing timeout
• Overcomplicating with DP when greedy suffices
• Trying brute force leading to inefficiency