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

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

Problem Analysis

↓

Is problem overlapping subproblems?

No→Use Greedy

Yes↓

Is problem optimal substructure?

No→Use Recursion

Yes↓

Use Dynamic Programming

↓

Implement and Solve

Decide the approach by checking problem properties: overlapping subproblems and optimal substructure guide choice between recursion, DP, or greedy.

Execution Sample

DSA C++

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

Simple recursive Fibonacci calculation showing recursion without optimization.

Execution Table

Step	Call Stack	Current Call	Return Value	Action
1	fib(4)	fib(4)	?	Call fib(4)
2	fib(4) -> fib(3)	fib(3)	?	Call fib(3)
3	fib(4) -> fib(3) -> fib(2)	fib(2)	?	Call fib(2)
4	fib(4) -> fib(3) -> fib(2) -> fib(1)	fib(1)	1	Base case return 1
5	fib(4) -> fib(3) -> fib(2) -> fib(0)	fib(0)	0	Base case return 0
6	fib(4) -> fib(3) -> fib(2)	fib(2)	1	Return fib(1)+fib(0)=1
7	fib(4) -> fib(3) -> fib(1)	fib(1)	1	Base case return 1
8	fib(4) -> fib(3)	fib(3)	2	Return fib(2)+fib(1)=2
9	fib(4) -> fib(2)	fib(2)	?	Call fib(2) again (repeated)
10	fib(4) -> fib(2) -> fib(1)	fib(1)	1	Base case return 1
11	fib(4) -> fib(2) -> fib(0)	fib(0)	0	Base case return 0
12	fib(4) -> fib(2)	fib(2)	1	Return fib(1)+fib(0)=1
13	fib(4)	fib(4)	3	Return fib(3)+fib(2)=3
14	-	-	-	Recursion ends
15	DP memoization starts	fib(4)	?	Call fib(4) with memo
16	fib(4) -> fib(3)	fib(3)	?	Call fib(3) with memo
17	fib(4) -> fib(3) -> fib(2)	fib(2)	?	Call fib(2) with memo
18	fib(4) -> fib(3) -> fib(2) -> fib(1)	fib(1)	1	Base case return 1
19	fib(4) -> fib(3) -> fib(2) -> fib(0)	fib(0)	0	Base case return 0
20	fib(4) -> fib(3) -> fib(2)	fib(2)	1	Memo store fib(2)=1
21	fib(4) -> fib(3) -> fib(1)	fib(1)	1	Base case return 1
22	fib(4) -> fib(3)	fib(3)	2	Memo store fib(3)=2
23	fib(4) -> fib(2)	fib(2)	1	Return memo fib(2)=1 (no recompute)
24	fib(4)	fib(4)	3	Memo store fib(4)=3
25	-	-	-	DP ends
26	Greedy example: coin change	-	-	Choose largest coin repeatedly
27	Coins chosen	-	-	Coins: 25, 10, 1, 1, 1 (total 5 coins)
28	-	-	-	Greedy ends

💡 Recursion ends when base cases reached; DP ends after memoization; Greedy ends when amount is zero.

Variable Tracker

Variable	Start	After Step 6	After Step 13	After Step 24	After Step 27
fib(4) return	?	?	3	3	3
fib(3) return	?	?	2	2	2
fib(2) return	?	1	1	1	1
Memo array	empty	empty	empty	[_, _, 1, 2, 3]	[_, _, 1, 2, 3]
Coins chosen	empty	empty	empty	empty	[25, 10, 1, 1, 1]

Key Moments - 3 Insights

Why does the recursive Fibonacci call fib(2) twice?

Because recursion recomputes fib(2) each time it is needed, shown in steps 3 and 9, causing repeated work.

How does DP avoid repeated computation?

DP stores results in a memo array (step 20 and 24), so when fib(2) is needed again (step 23), it returns stored value instantly.

When is greedy approach suitable?

Greedy works when local choices lead to global optimum, like coin change with standard coins (step 26-27), but not all problems fit this.

Visual Quiz - 3 Questions

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

A 1

B 3

C 2

D Undefined

💡 Hint

Check the 'Return Value' column at step 8 in the execution_table.

At which step does DP memoization store the value of fib(4)?

A Step 20

B Step 24

C Step 22

D Step 26

💡 Hint

Look for 'Memo store fib(4)' in the 'Action' column of execution_table.

If the problem has no overlapping subproblems, which approach is chosen according to the concept flow?

A Greedy

B Recursion

C Dynamic Programming

D Backtracking

💡 Hint

Refer to the concept_flow ASCII diagram decision after checking overlapping subproblems.

Concept Snapshot

DP vs Recursion vs Greedy Quick Guide:
- Recursion: Simple, solves by calling itself, but may repeat work.
- DP: Uses memoization or tabulation to avoid repeated work in overlapping subproblems.
- Greedy: Makes best local choice, works if problem has greedy-choice property.
- Choose DP if overlapping subproblems and optimal substructure exist.
- Choose Greedy if no overlapping subproblems and local optimum leads to global.
- Otherwise, use plain recursion or other methods.

Full Transcript

This lesson compares three problem-solving tools: recursion, dynamic programming (DP), and greedy algorithms. We start by analyzing the problem to see if it has overlapping subproblems and optimal substructure. If yes, DP is best because it stores results to avoid repeated work. If no overlapping subproblems, greedy may work by making local best choices. Otherwise, recursion is used but may be inefficient. The example of Fibonacci shows recursion calling fib(2) twice, causing repeated work. DP stores fib(2) result to reuse it. Greedy example shows coin change picking largest coins first. The concept flow diagram guides which tool to pick based on problem properties.

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 without memoization

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

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

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid recomputation, ideal for overlapping subproblems and optimal substructure.

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

2. Which of the following is the correct syntax to implement memoization in C++ recursion?

easy

A. Use a while loop instead of recursion

B. Use a for loop inside the recursive function

C. Call the recursive function twice without storing results

D. Use a global array or vector to store results and check before recursion

Solution

1. Step 1: Understand memoization concept

   Memoization stores results of recursive calls to avoid repeated work.

2. Step 2: Identify correct syntax usage

   Using a global or passed array/vector to save results and checking it before recursion is the correct way.

3. Final Answer:

   Use a global array or vector to store results and check before recursion -> Option D

4. Quick Check:

   Memoization = store results before recursion [OK]

Hint: Memoize by storing results in array before recursive calls [OK]

Common Mistakes:

• Not storing results causing repeated calculations
• Using loops inside recursion incorrectly
• Calling recursion multiple times without memo

3. What is the output of the following C++ code snippet?

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

int main() {
  std::cout << fib(4);
  return 0;
}

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1)+fib(0)) + 1 = (1+0)+1=2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output

   The program prints 3 as the result of fib(4).

3. Final Answer:

   3 -> Option C

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Trace small inputs stepwise to find Fibonacci output [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Adding wrong Fibonacci numbers
• Assuming fib(4) equals 4

4. Identify the error in the following code snippet implementing a greedy approach for coin change:

int coinChange(int amount, vector<int>& coins) {
  int count = 0;
  for (int i = 0; i < coins.size(); i++) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return count;
}

medium

A. Coins vector is not sorted in descending order

B. Using while loop inside for loop is incorrect

C. Function should return amount, not count

D. No error, code is correct

Solution

1. Step 1: Analyze greedy coin change logic

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

2. Step 2: Identify error in code

   The code loops coins in given order; if coins are not sorted descending, greedy fails to minimize count.

3. Final Answer:

   Coins vector is not sorted in descending order -> Option A

4. Quick Check:

   Greedy coin change needs descending sorted coins [OK]

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

Common Mistakes:

• Not sorting coins descending
• Returning wrong variable
• Thinking while loop inside for is wrong

5. You want to find the minimum number of coins to make a given amount using coins of denominations [1, 3, 4]. Which approach is best and why?

hard

A. Greedy approach because picking largest coin first always works

B. Dynamic Programming to store minimum coins needed for sub-amounts

C. Simple recursion without memoization to try all combinations

D. Brute force by checking all subsets of coins

Solution

1. Step 1: Understand problem requirements

   We want minimum coins for amount using coins [1,3,4]. Greedy fails here because picking largest coin first may not give minimum coins.

2. Step 2: Choose best approach

   Dynamic Programming stores minimum coins for all smaller amounts, building up to the target efficiently and correctly.

3. Final Answer:

   Dynamic Programming to store minimum coins needed for sub-amounts -> Option B

4. Quick Check:

   Minimum coins with tricky denominations = DP [OK]

Hint: Use DP when greedy fails to find minimum coins [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Using recursion without memo causing slow code
• Trying brute force which is inefficient