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

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

Problem Given

↓

Is problem optimal substructure?

No→Use Greedy

Yes↓

Is problem overlapping subproblems?

No→Use Recursion

Yes↓

Use Dynamic Programming

↓

Solution Found

Decide which method to use by checking problem properties: optimal substructure and overlapping subproblems.

Execution Sample

DSA Java

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

Simple recursive Fibonacci calculation showing overlapping subproblems.

Execution Table

Step	Call Stack	Current Call	Action	Result/Return	Notes
1	fib(4)	fib(4)	Check n<=1? No		Start with fib(4)
2	fib(4) -> fib(3)	fib(3)	Check n<=1? No		Call fib(3) from fib(4)
3	fib(4) -> fib(3) -> fib(2)	fib(2)	Check n<=1? No		Call fib(2) from fib(3)
4	fib(4) -> fib(3) -> fib(2) -> fib(1)	fib(1)	Check n<=1? Yes	1	Base case returns 1
5	fib(4) -> fib(3) -> fib(2) -> fib(0)	fib(0)	Check n<=1? Yes	0	Base case returns 0
6	fib(4) -> fib(3) -> fib(2)	fib(2)	Return fib(1)+fib(0)	1	fib(2) = 1 + 0 = 1
7	fib(4) -> fib(3) -> fib(1)	fib(1)	Check n<=1? Yes	1	Base case returns 1
8	fib(4) -> fib(3)	fib(3)	Return fib(2)+fib(1)	2	fib(3) = 1 + 1 = 2
9	fib(4) -> fib(2)	fib(2)	Check n<=1? No		Call fib(2) again (repeated)
10	fib(4) -> fib(2) -> fib(1)	fib(1)	Check n<=1? Yes	1	Base case returns 1
11	fib(4) -> fib(2) -> fib(0)	fib(0)	Check n<=1? Yes	0	Base case returns 0
12	fib(4) -> fib(2)	fib(2)	Return fib(1)+fib(0)	1	fib(2) = 1 + 0 = 1
13	fib(4)	fib(4)	Return fib(3)+fib(2)	3	fib(4) = 2 + 1 = 3
14					All calls returned, recursion ends

💡 fib(4) fully computed with recursive calls and returns.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	Final
n	4	1	2	3	2	4
Return Value			1	2	1	3

Key Moments - 3 Insights

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

Because recursion repeats calls without remembering past results, as seen in steps 3 and 9 in the execution_table.

When should we use Dynamic Programming instead of plain recursion?

When the problem has overlapping subproblems, like Fibonacci, to avoid repeated work shown by repeated calls in the execution_table.

Why is Greedy not used for Fibonacci?

Because Fibonacci does not have the greedy-choice property; it requires considering all subproblems, so greedy would fail to find correct results.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of fib(3) at step 8?

A 2

B 1

C 3

D 0

💡 Hint

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

At which step does the recursion start returning values back up the call stack?

A Step 6

B Step 1

C Step 4

D Step 14

💡 Hint

Look for the first step where 'Return' appears in the 'Result/Return' column.

If we add memoization to this recursion, how would the execution_table change?

A The recursion depth would increase

B Repeated calls like fib(2) at step 9 would be avoided

C More base cases would be added

D The return values would change

💡 Hint

Memoization stores results to prevent repeated calls, affecting repeated calls in execution_table.

Concept Snapshot

DP vs Recursion vs Greedy:
- Check if problem has optimal substructure.
- If no, try Greedy (make best local choice).
- If yes, check overlapping subproblems.
- If no overlap, use Recursion.
- If overlap, use Dynamic Programming (store results).
- DP avoids repeated work recursion does.

Full Transcript

This visual execution shows how to choose between Dynamic Programming, Recursion, and Greedy methods. We start by checking if the problem has optimal substructure. If not, greedy algorithms are suitable. If yes, we check for overlapping subproblems. Without overlap, recursion works. With overlap, dynamic programming is best to avoid repeated calculations. The example traces recursive Fibonacci calls, showing repeated calls to fib(2). This repetition highlights why DP is better here. Key moments clarify common confusions about repeated calls and method choice. The quiz tests understanding of recursion steps and memoization effects.

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