DP vs Recursion vs Greedy Choosing the Right Tool in DSA Go - 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 tool by checking problem properties: optimal substructure, overlapping subproblems, and greedy choice property.

Execution Sample

DSA Go

func fibRec(n int) int {
  if n <= 1 {
    return n
  }
  return fibRec(n-1) + fibRec(n-2)
}

This recursive function calculates Fibonacci numbers by calling itself twice for each n.

Execution Table

Step	Operation	Call Stack	Return Value	Notes
1	fibRec(3) called	[fibRec(3)]	-	Start computing fib(3)
2	fibRec(2) called	[fibRec(3), fibRec(2)]	-	fib(3) calls fib(2)
3	fibRec(1) called	[fibRec(3), fibRec(2), fibRec(1)]	1	Base case n=1 returns 1
4	fibRec(0) called	[fibRec(3), fibRec(2), fibRec(0)]	0	Base case n=0 returns 0
5	fibRec(2) returns	[fibRec(3)]	1	fib(2) = fib(1)+fib(0) = 1+0=1
6	fibRec(1) called	[fibRec(3), fibRec(1)]	1	fib(3) calls fib(1)
7	fibRec(3) returns	[]	2	fib(3) = fib(2)+fib(1) = 1+1=2
8	fibRec(3) done	[]	2	Final result fib(3) = 2

💡 All recursive calls resolved, final Fibonacci number returned.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 7	Final
Call Stack	[]	[fibRec(3)]	[fibRec(3), fibRec(2)]	[fibRec(3)]	[]	[]
Return Value	-	-	-	1	2	2

Key Moments - 3 Insights

Why does fibRec(1) get called twice in recursion?

Because recursion repeats calls without saving results, as seen in steps 3 and 6 in execution_table, causing repeated work.

When should we use DP instead of plain recursion?

When the problem has overlapping subproblems like Fibonacci, DP saves results to avoid repeated calls, unlike recursion shown here.

How do we know if greedy approach works?

If the problem has the greedy choice property, meaning local optimal choices lead to global optimum, then greedy is suitable; otherwise, use DP or recursion.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of fibRec(2) at step 5?

A 0

B 1

C 2

D 3

💡 Hint

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

At which step does the call stack become empty?

A Step 7

B Step 5

C Step 8

D Step 3

💡 Hint

Look at the 'Call Stack' column and find when it shows [].

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

A Fewer repeated calls, smaller call stack

B More calls and bigger call stack

C No change in calls or stack

D Calls become iterative

💡 Hint

Memoization avoids repeated calls by saving results, reducing call stack growth.

Concept Snapshot

DP vs Recursion vs Greedy Quick Guide:
- Recursion: simple, solves by calling itself, but repeats work.
- DP: recursion + memoization/tabulation, saves results to avoid repeats.
- Greedy: picks best local choice, fast but only works if problem allows.
- Choose DP if overlapping subproblems exist.
- Choose Greedy if greedy choice property holds.
- Otherwise, use recursion or DP.

Full Transcript

This visual guide helps choose between Dynamic Programming, Recursion, and Greedy algorithms. Start by checking if the problem has optimal substructure. If yes, check if subproblems overlap. If they do, use DP to save repeated work. If not, recursion is fine. Then check if greedy choice property holds; if yes, greedy is fastest. The example shows Fibonacci recursion with repeated calls and call stack growth. Memoization in DP avoids repeats. Greedy works only if local choices lead to global optimum.

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 parts.

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid repeated work, 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 memoization
• Confusing brute force with DP

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

easy

A. func factorial(n int) { if n == 0 { return 1 } return n * factorial(n-1) }

B. func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) }

C. func factorial(n int) int { if n == 0 { return 0 } return n * factorial(n-1) }

D. func factorial(n int) int { if n == 1 { return 0 } return n * factorial(n-1) }

Solution

1. Step 1: Check function return type and base case

   Factorial returns int, so function must return int. Base case for factorial is n == 0 returning 1.

2. Step 2: Verify recursive call and return statement

   Recursive call multiplies n by factorial(n-1). func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } matches correct signature and logic.

3. Final Answer:

   func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } -> Option B

4. Quick Check:

   Correct return type and base case = func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } [OK]

Hint: Check base case and return type carefully in recursion [OK]

Common Mistakes:

• Missing return type in function signature
• Incorrect base case value
• Returning wrong type or no return

3. What is the output of this Go code using recursion to compute Fibonacci numbers?

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

func main() {
  fmt.Println(fib(5))
}

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace fib(5) calls

   fib(5) = fib(4) + fib(3); 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; 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: Remember Fibonacci sequence: 0,1,1,2,3,5,8... [OK]

Common Mistakes:

• Confusing index starting point
• Miscomputing recursive calls
• Assuming fib(1) = 0

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

func coinChange(coins []int, amount int) int {
  count := 0
  for i := len(coins) - 1; i >= 0; i-- {
    for amount >= coins[i] {
      amount -= coins[i]
      count++
    }
  }
  if amount != 0 {
    return -1
  }
  return count
}

medium

A. Greedy may fail if coins are not canonical denominations

B. The inner loop should increment amount instead of decrement

C. Coins array must be sorted in ascending order

D. Return value should be amount instead of count

Solution

1. Step 1: Understand greedy coin change logic

   The code tries largest coins first, subtracting from amount until no longer possible.

2. Step 2: Identify limitation of greedy approach

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it may not find minimum coins or any solution.

3. Final Answer:

   Greedy may fail if coins are not canonical denominations -> Option A

4. Quick Check:

   Greedy correctness depends on coin set [OK]

Hint: Greedy coin change fails on non-standard coin sets [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Misunderstanding return values

5. You want to find the longest increasing subsequence (LIS) in an array. Which approach is best and why? A) Simple recursion tries all subsequences but is slow. B) Greedy picks local best but may miss global LIS. C) Dynamic Programming stores LIS lengths to avoid recomputation. D) Brute force enumerates all subsequences without optimization.

hard

A. Simple recursion is best for LIS

B. Greedy approach always finds LIS

C. Brute force is efficient for LIS

D. Dynamic Programming is best for LIS

Solution

1. Step 1: Analyze LIS problem nature

   LIS requires checking subsequences and their lengths. Simple recursion tries all but is exponential time.

2. Step 2: Compare approaches

   Greedy fails because local choices don't guarantee global LIS. DP stores LIS lengths for subproblems, improving efficiency.

3. Final Answer:

   Dynamic Programming is best for LIS -> Option D

4. Quick Check:

   LIS problem = DP best approach [OK]

Hint: Use DP for LIS to avoid exponential recursion [OK]

Common Mistakes:

• Choosing greedy for LIS
• Ignoring exponential time of recursion
• Thinking brute force is efficient