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

Recall & Review

beginner

What is recursion in problem solving?

Recursion is a method where a function calls itself to solve smaller parts of a problem until it reaches a simple base case.

beginner

What does DP (Dynamic Programming) help with?

DP helps solve problems by breaking them into smaller overlapping subproblems and storing their results to avoid repeated work.

beginner

When is a greedy algorithm the right choice?

A greedy algorithm works well when choosing the best option at each step leads to a global best solution without needing to reconsider choices.

intermediate

How do you decide between recursion and DP?

If subproblems overlap and repeat, use DP to save results. If subproblems are independent, simple recursion may be enough.

intermediate

Why might greedy algorithms fail sometimes?

Greedy algorithms can fail if local best choices do not lead to the best overall solution, especially when future steps depend on past decisions.

Which approach stores results of subproblems to avoid repeated work?

A Dynamic Programming

B Recursion without memoization

C Greedy Algorithm

D Brute Force

Dynamic Programming saves results of subproblems to avoid recalculating them.

When is a greedy algorithm most suitable?

A When recursion depth is too large

B When subproblems overlap

C When local choices lead to global optimum

D When all solutions must be checked

Greedy algorithms work best when local best choices lead to the best overall solution.

What is a base case in recursion?

A A greedy choice

B The simplest problem that stops recursion

C A repeated subproblem

D The largest problem to solve

Base case stops recursion by providing a simple answer.

Which method is best if subproblems do NOT overlap?

A Simple Recursion

B Dynamic Programming

C Greedy Algorithm

D Backtracking

If subproblems are independent, simple recursion is enough.

Why might DP be preferred over recursion?

A To increase recursion depth

B To make greedy choices

C To ignore base cases

D To avoid repeated calculations of the same subproblems

DP stores results to avoid recalculating subproblems, improving efficiency.

Explain how to choose between recursion, dynamic programming, and 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 a greedy algorithm works well and one where it fails.

Consider simple daily decisions vs complex ones needing full planning.