DP vs Recursion vs Greedy Choosing the Right Tool in DSA Javascript - Trade-offs & Analysis

Mental Model

We have three ways to solve problems: recursion tries all options, greedy picks the best now, and dynamic programming remembers past results to avoid repeats.

Analogy: Imagine choosing snacks: recursion tries every snack combination, greedy grabs the tastiest snack first, and dynamic programming remembers which snack combos worked best before to save time.

Recursion Tree:
     root
    /    \
  opt1  opt2
  /  \    |
...  ...  ...

Greedy Path:
start -> best choice -> next best -> end

DP Table:
+-----+-----+-----+
|  0  |  1  |  2  |
+-----+-----+-----+
| val | val | val |
+-----+-----+-----+

Dry Run Walkthrough

Input: Find max sum of non-adjacent numbers in [3, 2, 7, 10]

Goal: Choose the right method to find max sum without picking neighbors

Step 1: Recursion tries including 3 and excluding 2

Choices: include 3 -> skip 2 -> consider 7 and 10
Current sum: 3

Why: Recursion explores all options by choosing or skipping each number

Step 2: Recursion tries excluding 3 and including 2

Choices: skip 3 -> include 2 -> skip 7 -> include 10
Current sum: 12

Why: Recursion tries alternative path to find max sum

Step 3: Greedy picks 10 first as largest number

Pick 10, skip neighbors 7
Sum: 10

Why: Greedy picks locally best choice but may miss better combos

Step 4: Dynamic Programming builds table of max sums up to each index

DP: [3, max(3,2)=3, max(3+7,3)=10, max(10,3+10)=13]

Why: DP remembers best sums to avoid repeated work

Result:

DP final max sum: 13

Annotated Code

DSA Javascript

class MaxSumNonAdjacent {
  static maxSumRecursion(arr, index = 0) {
    if (index >= arr.length) return 0;
    // include current and skip next
    const include = arr[index] + MaxSumNonAdjacent.maxSumRecursion(arr, index + 2);
    // exclude current
    const exclude = MaxSumNonAdjacent.maxSumRecursion(arr, index + 1);
    return Math.max(include, exclude);
  }

  static maxSumGreedy(arr) {
    let sum = 0;
    let i = 0;
    while (i < arr.length) {
      sum += arr[i];
      i += 2; // skip next
    }
    return sum;
  }

  static maxSumDP(arr) {
    if (arr.length === 0) return 0;
    const dp = Array(arr.length).fill(0);
    dp[0] = Math.max(arr[0], 0);
    for (let i = 1; i < arr.length; i++) {
      const include = arr[i] + (i > 1 ? dp[i - 2] : 0);
      const exclude = dp[i - 1];
      dp[i] = Math.max(include, exclude);
    }
    return dp[arr.length - 1];
  }
}

const arr = [3, 2, 7, 10];
console.log("Recursion max sum:", MaxSumNonAdjacent.maxSumRecursion(arr));
console.log("Greedy max sum:", MaxSumNonAdjacent.maxSumGreedy(arr));
console.log("DP max sum:", MaxSumNonAdjacent.maxSumDP(arr));

const include = arr[index] + MaxSumNonAdjacent.maxSumRecursion(arr, index + 2);

include current element and skip next to avoid adjacency

const exclude = MaxSumNonAdjacent.maxSumRecursion(arr, index + 1);

exclude current element and move to next

return Math.max(include, exclude);

choose max sum between including or excluding current

sum += arr[i]; i += 2;

greedy picks current and skips next

dp[0] = Math.max(arr[0], 0);

initialize dp with first element

const include = arr[i] + (i > 1 ? dp[i - 2] : 0);

include current plus best sum two steps before

const exclude = dp[i - 1];

exclude current, keep previous best

dp[i] = Math.max(include, exclude);

store max sum at current index

Output

Recursion max sum: 13

Greedy max sum: 10

DP max sum: 13

Complexity Analysis

Time: O(n) for DP and Greedy because they scan the list once; O(2^n) for recursion because it explores all subsets

Space: O(n) for DP due to the table; O(n) for recursion call stack; O(1) for Greedy as it uses constant space

vs Alternative: DP is more efficient than recursion by avoiding repeated calculations; Greedy is fastest but may give wrong answers if problem needs global view

Edge Cases

empty array

returns 0 as no elements to pick

DSA Javascript

if (arr.length === 0) return 0;

array with one element

returns that element as max sum

DSA Javascript

dp[0] = Math.max(arr[0], 0);

all elements negative

returns max single element or 0 depending on implementation

DSA Javascript

Math.max(include, exclude);

When to Use This Pattern

When a problem asks for optimal choices with overlapping subproblems, consider dynamic programming; if it can be solved by making local best choices, greedy might work; if exploring all possibilities is needed, recursion fits.

Common Mistakes

Mistake: Using greedy approach on problems that require global optimization leads to wrong answers
Fix: Use dynamic programming to consider all subproblems and store results

Mistake: Not caching results in recursion causes exponential time
Fix: Use memoization or convert to dynamic programming

Summary

Compares recursion, greedy, and dynamic programming to solve optimization problems.

Use recursion for simple exploration, greedy for fast local decisions, and dynamic programming for overlapping subproblems.

Dynamic programming remembers past results to avoid repeated work, making it efficient for many problems.

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