DP vs Recursion vs Greedy Choosing the Right Tool in DSA Javascript - Build Both Approaches

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: Imagine you are helping a small delivery company decide the best way to pack their delivery boxes to maximize value without exceeding weight limits. They want to try different methods to see which works best.

🎯 Goal: You will create a simple program to solve the classic 'Knapsack problem' using three methods: recursion, dynamic programming (DP), and a greedy approach. You will see how each method works and compare their results.

📋 What You'll Learn

Create arrays for item weights and values

Set a maximum weight capacity

Implement a recursive function to find max value

Implement a dynamic programming solution for max value

Implement a greedy approach based on value-to-weight ratio

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Delivery companies and packing services often need to decide how to pack items efficiently to maximize value without exceeding weight limits.

💼 Career

Understanding recursion, dynamic programming, and greedy algorithms helps in solving optimization problems common in software engineering and data science roles.

1

Setup item weights, values, and capacity

Create three arrays called weights with values [2, 3, 4, 5], values with values [3, 4, 5, 6], and a variable capacity set to 5.

DSA Javascript

# Your code here

Hint

Use const to create arrays and a number variable exactly as shown.

2

Write a recursive function to find max value

Write a function called knapsackRecursive that takes index and remainingCapacity as parameters. It should return 0 if index is less than 0 or remainingCapacity is 0. Otherwise, if the weight at index is more than remainingCapacity, return the result of calling knapsackRecursive with index - 1 and the same remainingCapacity. Else, return the maximum of two calls: one excluding the current item, and one including the current item (adding its value and reducing capacity).

DSA Javascript

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 5;

// Write knapsackRecursive function here
# Your code here

Hint

Use a function with base cases for index and capacity, then choose max between including or excluding the current item.

3

Implement dynamic programming solution

Create a function called knapsackDP that uses a 2D array dp of size (weights.length + 1) x (capacity + 1). Initialize all values to 0. Use nested for loops to fill dp where dp[i][w] stores max value using first i items and capacity w. If the current item's weight is less than or equal to w, set dp[i][w] to max of excluding or including the item. Otherwise, copy the value from above. Return dp[weights.length][capacity].

DSA Javascript

function knapsackDP() {
    const n = weights.length;
    const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    return dp[n][capacity];
// Write knapsackGreedy function and print statements here

Hint

Use a 2D array and fill it row by row comparing including or excluding each item.

4

Implement greedy approach and print all results

Write a function called knapsackGreedy that creates an array of objects with weight, value, and ratio (value divided by weight). Sort this array in descending order by ratio. Then, iterate over the sorted array, adding items fully if they fit in the remaining capacity, summing their values. Return the total value. Finally, print the results of calling knapsackRecursive(weights.length - 1, capacity), knapsackDP(), and knapsackGreedy() with labels "Recursive:", "DP:", and "Greedy:" respectively.

DSA Javascript

Hint

Sort items by value-to-weight ratio, pick items while capacity allows, then print all results with labels.

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