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

Start Problem

↓

Is problem optimal substructure?

|Yes↓

Is problem overlapping subproblems?

↓

Use DP

↓

Is greedy choice property valid?

↓

Use Greedy

↓

Solve Problem

↓

End

Decide the right approach by checking problem properties: optimal substructure, overlapping subproblems, and greedy choice property.

Execution Sample

DSA C#

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

Simple recursive Fibonacci calculation showing overlapping subproblems without optimization.

Execution Table

Step	Operation	Call Stack	Subproblem Computed	Result Returned
1	Call FibRec(4)	[FibRec(4)]	Fib(4)	Pending
2	Call FibRec(3)	[FibRec(4), FibRec(3)]	Fib(3)	Pending
3	Call FibRec(2)	[FibRec(4), FibRec(3), FibRec(2)]	Fib(2)	Pending
4	Call FibRec(1)	[FibRec(4), FibRec(3), FibRec(2), FibRec(1)]	Fib(1)	1
5	Return FibRec(1)	[FibRec(4), FibRec(3), FibRec(2)]	Fib(1)	1
6	Call FibRec(0)	[FibRec(4), FibRec(3), FibRec(2), FibRec(0)]	Fib(0)	0
7	Return FibRec(0)	[FibRec(4), FibRec(3), FibRec(2)]	Fib(0)	0
8	Return FibRec(2)	[FibRec(4), FibRec(3)]	Fib(2)	1
9	Call FibRec(1)	[FibRec(4), FibRec(3), FibRec(1)]	Fib(1)	1
10	Return FibRec(1)	[FibRec(4), FibRec(3)]	Fib(1)	1
11	Return FibRec(3)	[FibRec(4)]	Fib(3)	2
12	Call FibRec(2)	[FibRec(4), FibRec(2)]	Fib(2)	Pending
13	Call FibRec(1)	[FibRec(4), FibRec(2), FibRec(1)]	Fib(1)	1
14	Return FibRec(1)	[FibRec(4), FibRec(2)]	Fib(1)	1
15	Call FibRec(0)	[FibRec(4), FibRec(2), FibRec(0)]	Fib(0)	0
16	Return FibRec(0)	[FibRec(4), FibRec(2)]	Fib(0)	0
17	Return FibRec(2)	[FibRec(4)]	Fib(2)	1
18	Return FibRec(4)	[]	Fib(4)	3
19	End	[]	-	-

💡 FibRec(4) returns 3 after computing all subproblems recursively.

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 11	After Step 18
Call Stack	[]	[FibRec(4), FibRec(3), FibRec(2), FibRec(1)]	[FibRec(4), FibRec(3)]	[FibRec(4)]	[]
Fib(1)	Pending	1	1	1	1
Fib(2)	Pending	Pending	1	1	1
Fib(3)	Pending	Pending	Pending	2	2
Fib(4)	Pending	Pending	Pending	Pending	3

Key Moments - 3 Insights

Why does FibRec(2) get computed multiple times?

Because recursion recomputes overlapping subproblems without saving results, as seen in steps 3 and 12 in the execution_table.

When should we prefer DP over plain recursion?

When the problem has overlapping subproblems and optimal substructure, DP saves repeated work by storing results, unlike recursion shown here.

Why can't greedy always solve problems like Fibonacci?

Greedy requires a local choice leading to global optimum, which Fibonacci lacks; it needs combining sub-results, so DP or recursion is needed.

Visual Quiz - 3 Questions

Look at the execution_table, what is the call stack at step 10?

A [FibRec(4), FibRec(3)]

B [FibRec(4), FibRec(3), FibRec(1)]

C [FibRec(4), FibRec(2)]

D [FibRec(4)]

💡 Hint

Check the 'Call Stack' column at step 10 in the execution_table.

At which step does FibRec(4) finally return its result?

A Step 11

B Step 17

C Step 18

D Step 19

💡 Hint

Look for the step where 'Return FibRec(4)' happens in the execution_table.

If we add memoization, how would the number of FibRec(2) calls change?

A It would stay the same

B It would reduce to one

C It would increase

D It would become zero

💡 Hint

Memoization stores results to avoid repeated calls, reducing duplicates as seen in variable_tracker.

Concept Snapshot

DP vs Recursion vs Greedy Quick Guide:
- Recursion: Simple, solves by calling itself, but repeats work.
- DP: Uses recursion + stores results to avoid repeats (overlapping subproblems).
- Greedy: Makes best local choice, works only if problem has greedy property.
Choose DP if overlapping subproblems exist.
Choose Greedy if local choices lead to global optimum.
Use recursion for simple or non-overlapping problems.

Full Transcript

This visual guide compares dynamic programming, recursion, and greedy approaches. It shows how recursion solves problems by calling itself repeatedly, often recomputing the same subproblems, as in Fibonacci calculation. Dynamic programming improves recursion by storing results to avoid repeated work when subproblems overlap. Greedy algorithms make the best local choice at each step but only work when this leads to a global optimum. The flowchart helps decide which method to use based on problem properties like optimal substructure and overlapping subproblems. The execution table traces recursive Fibonacci calls step-by-step, showing the call stack and results returned. Key moments clarify why recursion repeats work, when DP is better, and why greedy doesn't fit all problems. The quiz tests understanding of call stack states and effects of memoization. The snapshot summarizes when to use each approach simply.

Practice

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

easy

A. Simple Recursion

B. Dynamic Programming

C. Greedy Algorithm

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

   Overlapping subproblems mean 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 B

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

2. Which of the following C# code snippets correctly implements a greedy approach to find the maximum number of activities that don't overlap given start and end times arrays (assuming sorted by end time)?

easy

A. int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count);

B. int count = 0; for (int i = 0; i < start.Length; i++) { if (start[i] > end[i]) count++; } Console.WriteLine(count);

C. int count = 1; for (int i = 1; i < start.Length; i++) { if (end[i] >= start[i-1]) count++; } Console.WriteLine(count);

D. int count = 0; foreach (var s in start) { count += s; } Console.WriteLine(count);

Solution

1. Step 1: Understand greedy activity selection logic

   We select the first activity, then pick next activities starting after the last selected activity ends.

2. Step 2: Check code correctness

   int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); initializes count to 1, tracks lastEnd, and increments count only if start[i] >= lastEnd, updating lastEnd. This matches greedy logic.

3. Final Answer:

   the code that tracks lastEnd -> Option A

4. Quick Check:

   Greedy activity selection code = int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); [OK]

Hint: Pick next activity starting after last selected ends [OK]

Common Mistakes:

• Not sorting activities by end time before selection
• Comparing start[i] with wrong end time
• Counting activities incorrectly

3. What is the output of the following C# code that uses recursion to calculate Fibonacci numbers without memoization?

int Fib(int n) { if (n <= 1) return n; return Fib(n - 1) + Fib(n - 2); } Console.WriteLine(Fib(5));

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace recursive calls for Fib(5)

   Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0); Fib(1)=1, Fib(0)=0.

2. Step 2: Calculate values bottom-up

   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:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) = 5 by definition [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Miscomputing recursive sums
• Assuming memoization changes output

4. The following C# code attempts to solve the coin change problem using recursion but has a bug. What is the bug?

int CoinChange(int[] coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; int min = int.MaxValue; foreach (int coin in coins) { int res = CoinChange(coins, amount - coin); if (res >= 0 && res < min) min = 1 + res; } return min == int.MaxValue ? -1 : min; }

medium

A. No memoization causing repeated calculations

B. Incorrect base case for amount == 0

C. Returning -1 instead of 0 for amount < 0

D. Using foreach instead of for loop

Solution

1. Step 1: Analyze recursion and base cases

   Base cases are correct: 0 returns 0, negative returns -1. The recursion tries all coins.

2. Step 2: Identify missing optimization

   Without memoization, the function recalculates subproblems many times, causing inefficiency and possible stack overflow.

3. Final Answer:

   No memoization causing repeated calculations -> Option A

4. Quick Check:

   Missing memoization = No memoization causing repeated calculations [OK]

Hint: Add memo dictionary to avoid repeated calls [OK]

Common Mistakes:

• Thinking base cases are wrong
• Believing loop type causes bug
• Ignoring performance issues

5. You want to find the minimum number of coins needed to make a given amount using coins of different denominations. Which approach is best and why?

hard

A. Greedy algorithm may fail for some coin sets

B. Simple iteration misses subproblem reuse

C. Recursion without memoization is inefficient

D. Dynamic programming ensures optimal solution efficiently

Solution

1. Step 1: Evaluate greedy approach limitations

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it can fail to find minimum coins.

2. Step 2: Consider recursion and iteration drawbacks

   Recursion without memoization repeats work; simple iteration without storing results misses subproblem reuse.

3. Step 3: Understand dynamic programming benefits

   DP with bottom-up tabulation stores minimum coins for all amounts up to target, guaranteeing optimal and efficient solution.

4. Final Answer:

   Dynamic programming ensures optimal solution efficiently -> Option D

5. Quick Check:

   Minimum coins problem = DP bottom-up [OK]

Hint: Use DP tabulation for guaranteed minimum coins [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring performance of recursion
• Not storing intermediate results