DP vs Recursion vs Greedy Choosing the Right Tool in DSA Python - Key Differences

Recall & Review

beginner

What is the main difference between recursion and dynamic programming?

Recursion solves problems by breaking them into smaller subproblems and calling itself, but may repeat work. Dynamic programming improves recursion by storing results of subproblems to avoid repeated work.

beginner

When is a greedy algorithm the right choice?

When the problem has the greedy choice property, meaning a local optimal choice leads to a global optimal solution without needing to reconsider previous choices.

intermediate

What problem characteristic suggests using dynamic programming?

When the problem has overlapping subproblems and optimal substructure, meaning subproblems repeat and the overall solution depends on solutions to subproblems.

beginner

Why might pure recursion be inefficient for some problems?

Because it may solve the same subproblems multiple times, leading to exponential time complexity without storing intermediate results.

intermediate

Give an example where greedy algorithms fail but dynamic programming works.

The coin change problem with arbitrary coin denominations: greedy may not find minimum coins, but dynamic programming finds the optimal solution.

Which approach stores results of subproblems to avoid repeated work?

A Dynamic Programming

B Greedy Algorithm

C Pure Recursion

D Brute Force

Dynamic Programming saves results of subproblems to avoid recalculating them.

When is greedy algorithm guaranteed to give an optimal solution?

A When problem has overlapping subproblems

B When problem has greedy choice property

C When problem has no subproblems

D Always

Greedy algorithms work optimally when the problem has the greedy choice property.

What is a key sign that recursion alone may be inefficient?

A No subproblems

B No base case

C Greedy choice property

D Overlapping subproblems

Overlapping subproblems cause recursion to repeat work, making it inefficient.

Which method is best when subproblems do not overlap?

A Recursion with memoization

B Dynamic Programming

C Greedy Algorithm

D Brute Force

Greedy algorithms are efficient when subproblems do not overlap and local choices lead to global optimum.

Which problem is a classic example where greedy fails but DP works?

A Coin change with arbitrary coins

B Sorting numbers

C Finding max in array

D Binary search

Coin change with arbitrary denominations requires DP for optimal solution; greedy may fail.

Explain how to decide between using recursion, dynamic programming, or greedy algorithms for a problem.

Think about problem structure and if subproblems repeat or if local choices are enough.

Describe a real-life example where greedy algorithm works well and one where dynamic programming is better.

Consider simple daily decisions vs complex planning with repeated choices.

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