DP vs Recursion vs Greedy Choosing the Right Tool in DSA Python - 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?

|Yes↓

Use Greedy

↓

Solution Found

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

Execution Sample

DSA Python

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

Calculates Fibonacci number using simple recursion.

Execution Table

Step	Call Stack	Current Call	Return Value	Action
1	fib_recursive(4)	fib_recursive(4)	?	Call fib_recursive(4)
2	fib_recursive(4) -> fib_recursive(3)	fib_recursive(3)	?	Call fib_recursive(3)
3	fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2)	fib_recursive(2)	?	Call fib_recursive(2)
4	fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2) -> fib_recursive(1)	fib_recursive(1)	1	Base case return 1
5	fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2) -> fib_recursive(0)	fib_recursive(0)	0	Base case return 0
6	fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2)	fib_recursive(2)	1	Return 1 + 0 = 1
7	fib_recursive(4) -> fib_recursive(3) -> fib_recursive(1)	fib_recursive(1)	1	Base case return 1
8	fib_recursive(4) -> fib_recursive(3)	fib_recursive(3)	2	Return 1 + 1 = 2
9	fib_recursive(4) -> fib_recursive(2)	fib_recursive(2)	?	Call fib_recursive(2) again (repeated)
10	fib_recursive(4) -> fib_recursive(2) -> fib_recursive(1)	fib_recursive(1)	1	Base case return 1
11	fib_recursive(4) -> fib_recursive(2) -> fib_recursive(0)	fib_recursive(0)	0	Base case return 0
12	fib_recursive(4) -> fib_recursive(2)	fib_recursive(2)	1	Return 1 + 0 = 1
13	fib_recursive(4)	fib_recursive(4)	3	Return 2 + 1 = 3
14	-	-	-	All calls complete, final result 3

💡 All recursive calls resolved, fib_recursive(4) returns 3

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	Final
Call Stack Depth	1	4	3	2	2	0
fib_recursive(4) return	?	?	?	?	?	3
fib_recursive(3) return	?	?	2	2	2	2
fib_recursive(2) return	?	1	1	1	1	1

Key Moments - 3 Insights

Why does fib_recursive(2) get called twice?

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

When should we use DP instead of recursion?

Use DP when the problem has overlapping subproblems like repeated fib_recursive(2) calls, to save results and avoid repeated work.

What is the greedy choice property?

It means making the best local choice leads to a global optimum, so greedy algorithms work only if this property holds.

Visual Quiz - 3 Questions

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

A 2

B 1

C 3

D 0

💡 Hint

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

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

A Step 1

B Step 4

C Step 9

D Step 14

💡 Hint

Look for the first base case return in the execution_table.

If we use DP (memoization) for Fibonacci, how would the execution_table change?

A More repeated calls would appear

B Base cases would be skipped

C Calls like fib_recursive(2) would be computed once and reused

D Return values would be incorrect

💡 Hint

Refer to the repeated calls of fib_recursive(2) at steps 3 and 9 in the execution_table.

Concept Snapshot

DP vs Recursion vs Greedy Quick Guide:
- Recursion: Simple, solves by calling itself, but may repeat work.
- DP: Recursion + saving results (memoization) to avoid repeats.
- Greedy: Make best local choice if it leads to global best.
- Use DP if overlapping subproblems exist.
- Use Greedy only if greedy choice property holds.
- Choose based on problem structure for efficiency.

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, simple recursion works. If the greedy choice property holds, greedy algorithms can be used for faster solutions. The example of Fibonacci recursion shows repeated calls causing inefficiency. DP would save these results. The execution table traces each recursive call and return, showing how the call stack grows and shrinks. Key moments clarify why repeated calls happen and when to use DP. The quiz tests understanding of return values, recursion flow, and DP benefits. The snapshot summarizes when and why to use each approach.

Practice

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

easy

A. Brute Force

B. Greedy Algorithm

C. Dynamic Programming

D. Simple Recursion without memoization

Solution

1. Step 1: Understand problem properties

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

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 problem needs global optimization
• Using simple recursion causing repeated calculations
• Confusing brute force with efficient methods

2. Which of the following Python function definitions correctly implements a recursive Fibonacci function?

easy

A. def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)

B. def fib(n): for i in range(n): return fib(i-1) + fib(i-2)

C. def fib(n): while n > 1: n -= 1 return n

D. def fib(n): return n + fib(n-1)

Solution

1. Step 1: Check base case and recursion

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) correctly returns n if n <= 1, else calls fib(n-1) + fib(n-2).

2. Step 2: Verify other options

   Options B, C, and D have syntax or logic errors: B uses for loop wrongly, C uses while without recursion, D causes infinite recursion.

3. Final Answer:

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) -> Option A

4. Quick Check:

   Correct recursive base and calls = def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) [OK]

Hint: Base case + two recursive calls = correct Fibonacci recursion [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursion incorrectly
• Wrong return statements inside recursion

3. What is the output of the following code?

def max_sum(arr, n):
    if n == 0:
        return 0
    elif n == 1:
        return arr[0]
    else:
        return max(max_sum(arr, n-1), max_sum(arr, n-2) + arr[n-1])

print(max_sum([3, 2, 7, 10], 4))

medium

A. 13

B. 17

C. 20

D. 10

Solution

1. Step 1: Understand function logic

   max_sum returns max sum of non-adjacent elements from first n elements.

2. Step 2: Trace calls for n=4

   max_sum(arr,4) = max(max_sum(arr,3), max_sum(arr,2) + arr[3]) max_sum(arr,3) = max(max_sum(arr,2), max_sum(arr,1) + arr[2]) max_sum(arr,2) = max(max_sum(arr,1), max_sum(arr,0) + arr[1]) Calculate bottom-up: max_sum(arr,0)=0 max_sum(arr,1)=3 max_sum(arr,2)=max(3,0+2)=3 max_sum(arr,3)=max(3,3+7)=10 max_sum(arr,4)=max(10,3+10)=13

3. Final Answer:

   13 -> Option A

4. Quick Check:

   Max sum non-adjacent = 13 [OK]

Hint: Trace recursion bottom-up for max sum non-adjacent [OK]

Common Mistakes:

• Adding adjacent elements mistakenly
• Confusing indices in recursion
• Ignoring base cases

4. The following code tries to solve the coin change problem using recursion but has an error. What is the error?

def coin_change(coins, amount):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    count = 0
    for coin in coins:
        count += coin_change(coins, amount - coin)
    return count

print(coin_change([1, 2], 3))

medium

A. It does not handle negative amounts correctly

B. It counts duplicate combinations multiple times

C. It misses base case for amount == 1

D. It uses iteration instead of recursion

Solution

1. Step 1: Analyze recursion logic

   The function counts ways to make amount by subtracting coins recursively.

2. Step 2: Identify counting duplicates

   Because it tries all coins at each step without order control, it counts same combinations in different orders multiple times.

3. Final Answer:

   It counts duplicate combinations multiple times -> Option B

4. Quick Check:

   Duplicates counted due to unordered recursion [OK]

Hint: Unordered recursion counts duplicates; use order or DP to fix [OK]

Common Mistakes:

• Assuming base cases are missing
• Confusing negative amount handling
• Thinking iteration replaces recursion

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

hard

A. Brute force trying all combinations without optimization

B. Simple recursion without memoization for clarity

C. Greedy algorithm because always picking largest coin works

D. Dynamic Programming to store and reuse subproblem results

Solution

1. Step 1: Understand problem requirements

   We want minimum coins to make amount, which requires checking all combinations to find optimal.

2. Step 2: Evaluate approaches

   Greedy fails here because picking largest coin first may not yield minimum coins (e.g., amount=6, greedy picks 4+1+1=3 coins, but 3+3=2 coins is better). Simple recursion repeats subproblems causing inefficiency. DP stores results to avoid repeated work and finds optimal solution efficiently.

3. Final Answer:

   Dynamic Programming to store and reuse subproblem results -> Option D

4. Quick Check:

   Minimum coins with overlapping subproblems = DP [OK]

Hint: Use DP for minimum coins; greedy can fail with some denominations [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring efficiency of memoization
• Using brute force causing timeouts