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

Mental Model

We solve problems by breaking them down into smaller parts. Recursion tries all ways, greedy picks the best now, and DP remembers past results to avoid repeats.

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

Recursion Tree:
       root
      /    \
    sub1   sub2
   /   \     \
sub1a sub1b  sub2a

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

DP Table:
+-----+-----+-----+
|  0  |  1  |  2  |
+-----+-----+-----+
|memo0|memo1|memo2|
+-----+-----+-----+

Dry Run Walkthrough

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

Goal: Compare how recursion, greedy, and DP solve this problem and see which is best

Step 1: Recursion tries including 3, then skips 2, tries 7 and 10

Recursion tree explores: include 3 -> skip 2 -> include 7 -> include 10
Partial sums: 3 + 7 + 10 = 20 (invalid because 7 and 10 are adjacent)

Why: Recursion explores all combos to find max sum without adjacency

Step 2: Greedy picks from the end, taking every other element

Greedy picks 10 (index 3), skips 7, picks 2 (index 1)
Sum = 10 + 2 = 12

Why: Greedy picks biggest number now, hoping for best total

Step 3: DP builds memo table storing max sum at each index

DP table: index 0=3, index 1=max(3,2)=3, index 2=max(3+7,3)=10, index 3=max(3+10,10)=13

Why: DP remembers best sums to avoid repeated work and adjacency

Step 4: Compare results: recursion finds max sum 13, greedy gets 12, DP gets 13

Final max sum = 13 from DP and recursion; greedy gets 12 (suboptimal here)

Why: DP and recursion guarantee correct max sum; greedy may fail if local best is not global best

Result:

DP table: 3 -> 3 -> 10 -> 13
Max sum without adjacent numbers = 13

Annotated Code

DSA Java

public class MaxNonAdjacentSum {
    // Recursive solution
    public static int maxSumRec(int[] nums, int index) {
        if (index < 0) return 0;
        if (index == 0) return nums[0];
        // Include current number and skip one
        int include = nums[index] + maxSumRec(nums, index - 2);
        // Exclude current number
        int exclude = maxSumRec(nums, index - 1);
        return Math.max(include, exclude);
    }

    // Greedy solution (not always correct)
    public static int maxSumGreedy(int[] nums) {
        int sum = 0;
        int i = nums.length - 1;
        while (i >= 0) {
            sum += nums[i];
            i -= 2; // skip adjacent
        }
        return sum;
    }

    // DP solution
    public static int maxSumDP(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int include = nums[i];
            if (i > 1) include += dp[i - 2];
            int exclude = dp[i - 1];
            dp[i] = Math.max(include, exclude);
        }
        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 7, 10};
        System.out.println("Recursion max sum: " + maxSumRec(nums, nums.length - 1));
        System.out.println("Greedy max sum: " + maxSumGreedy(nums));
        System.out.println("DP max sum: " + maxSumDP(nums));
    }
}

int include = nums[index] + maxSumRec(nums, index - 2);

include current number and skip adjacent to avoid adjacency

int exclude = maxSumRec(nums, index - 1);

exclude current number and check previous

sum += nums[i]; i -= 2;

greedy picks current number and skips next to avoid adjacency

int include = nums[i]; if (i > 1) include += dp[i - 2];

include current number plus best sum two steps before

int exclude = dp[i - 1];

exclude current number, take best sum from previous

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

store max sum at current index

Output

Recursion max sum: 13

Greedy max sum: 12

DP max sum: 13

Complexity Analysis

Time: O(n) because DP and greedy scan the list once; recursion is exponential without memoization

Space: O(n) for DP array; O(n) call stack for recursion; O(1) for greedy

vs Alternative: DP is better than recursion alone because it avoids repeated work; greedy is fastest but can fail on some inputs

Edge Cases

Empty list

All methods return 0 safely

DSA Java

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

Single element list

Return that element as max sum

DSA Java

if (index == 0) return nums[0];

All elements equal

DP and recursion correctly pick non-adjacent elements for max sum; greedy may pick wrong

DSA Java

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

When to Use This Pattern

When a problem asks for optimal choices with constraints and overlapping subproblems, consider DP; if choices are simple and local, greedy might work; recursion is a natural but inefficient start.

Common Mistakes

Mistake: Using greedy thinking for problems where local best choice is not global best
Fix: Use DP or recursion with memoization to ensure global optimality

Mistake: Not handling base cases in recursion leading to errors
Fix: Add base cases for index < 0 and index == 0

Summary

Compares recursion, greedy, and DP approaches to solve optimization problems with constraints.

Use recursion to explore all options, greedy for simple local decisions, and DP when overlapping subproblems exist.

DP remembers past results to avoid repeated work and guarantees optimal solutions unlike greedy.

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion

D. Brute Force

Solution

1. Step 1: Understand problem properties

   Overlapping subproblems means the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller parts.

2. Step 2: Match approach to properties

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for these properties.

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
• Confusing optimal substructure with greedy choice property

2. Which of the following Java method signatures correctly represents a recursive function to compute factorial?

easy

A. public static int factorial(int n) { if (n == 1) return 0; else return n + factorial(n - 1); }

B. public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }

C. public static int factorial(int n) { for (int i = 1; i <= n; i++) return i; }

D. public static int factorial(int n) { while (n > 0) n = n - 1; return n; }

Solution

1. Step 1: Check base case correctness

   Factorial base case is 0! = 1, so if (n == 0) return 1 is correct.

2. Step 2: Check recursive call and calculation

   Factorial(n) = n * factorial(n-1) is correct recursive formula.

3. Final Answer:

   public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive multiplication = public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Factorial recursion multiplies n by factorial(n-1) with base n=0 [OK]

Common Mistakes:

• Wrong base case (e.g., returning 0 instead of 1)
• Using loops instead of recursion
• Returning addition instead of multiplication

3. What will be the output of the following Java code snippet?

public class Test {
  public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 3

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2). fib(3) = fib(2) + fib(1), fib(2) = fib(1) + fib(0).

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1, so fib(2)=1+0=1, fib(3)=1+1=2, fib(4)=2+1=3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Fibonacci(4) = 3 by adding previous two Fibonacci numbers [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Adding wrong recursive results
• Assuming fib(4) = 5 (fibonacci(5))

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

public static int minCoins(int[] coins, int amount) {
  int count = 0;
  for (int coin : coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

medium

A. Missing base case for amount = 0

B. Should use recursion instead of loops

C. Coins array must be sorted in descending order

D. Count variable should be reset inside the loop

Solution

1. Step 1: Understand greedy coin change logic

   Greedy picks largest coin first to minimize count. Coins must be sorted descending for this to work.

2. Step 2: Check code for sorting

   Code does not sort coins, so if coins are unsorted, greedy picks smaller coins first, leading to wrong answer.

3. Final Answer:

   Coins array must be sorted in descending order -> Option C

4. Quick Check:

   Greedy coin change needs descending sorted coins [OK]

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

Common Mistakes:

• Not sorting coins before greedy selection
• Using recursion unnecessarily
• Resetting count inside loop causing wrong count

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?

int[] arr = {2,3,1,1,4};

hard

A. Use Dynamic Programming to store minimum jumps for each index

B. Use simple recursion to try all jump combinations

C. Use Brute Force to check every path

D. Use Greedy approach to jump to the farthest reachable index

Solution

1. Step 1: Analyze problem nature

   Minimum jumps problem can be solved efficiently by greedy because at each step, jumping to the farthest reachable index reduces total jumps.

2. Step 2: Compare approaches

   Recursion or DP works but are slower. Greedy gives optimal solution in linear time for this problem.

3. Final Answer:

   Use Greedy approach to jump to the farthest reachable index -> Option D

4. Quick Check:

   Minimum jumps = Greedy farthest jump [OK]

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

Common Mistakes:

• Using recursion causing timeouts
• Overcomplicating with DP when greedy suffices
• Ignoring problem constraints for greedy validity