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

↓

Can problem be divided into smaller subproblems?

↓

Is there overlapping subproblems?

↓

Use DP (Memoization or Tabulation)

↓

Solve subproblems efficiently

↓

Combine results for final answer

↓

Done

This flow shows how to decide between recursion, dynamic programming, and greedy methods based on problem properties.

Execution Sample

DSA C

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

Simple recursion to compute Fibonacci number, recalculating subproblems multiple times.

Execution Table

Step	Operation	Nodes in Call Stack	Subproblem Computed	Result Returned	Visual State
1	Call fib(4)	fib(4)	None yet	Pending	Call stack: fib(4)
2	Call fib(3)	fib(4) -> fib(3)	None yet	Pending	Call stack: fib(4), fib(3)
3	Call fib(2)	fib(4) -> fib(3) -> fib(2)	None yet	Pending	Call stack: fib(4), fib(3), fib(2)
4	Call fib(1)	fib(4) -> fib(3) -> fib(2) -> fib(1)	fib(1) = 1	1	Return fib(1)=1, pop fib(1)
5	Call fib(0)	fib(4) -> fib(3) -> fib(2) -> fib(0)	fib(0) = 0	0	Return fib(0)=0, pop fib(0)
6	Return fib(2) = fib(1)+fib(0)	fib(4) -> fib(3)	fib(2) = 1	1	Return fib(2)=1, pop fib(2)
7	Call fib(1)	fib(4) -> fib(3) -> fib(1)	fib(1) = 1	1	Return fib(1)=1, pop fib(1)
8	Return fib(3) = fib(2)+fib(1)	fib(4)	fib(3) = 2	2	Return fib(3)=2, pop fib(3)
9	Call fib(2)	fib(4) -> fib(2)	fib(2) recomputed	Pending	Call stack: fib(4), fib(2)
10	Call fib(1)	fib(4) -> fib(2) -> fib(1)	fib(1) = 1	1	Return fib(1)=1, pop fib(1)
11	Call fib(0)	fib(4) -> fib(2) -> fib(0)	fib(0) = 0	0	Return fib(0)=0, pop fib(0)
12	Return fib(2) = fib(1)+fib(0)	fib(4)	fib(2) = 1	1	Return fib(2)=1, pop fib(2)
13	Return fib(4) = fib(3)+fib(2)	None	fib(4) = 3	3	Return fib(4)=3, call stack empty

💡 All recursive calls completed, final result fib(4) = 3 returned

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 13
fib(4)	Not called	Pending	Pending	Pending	3
fib(3)	Not called	Pending	1	2	Returned
fib(2)	Not called	Pending	1	Recomputed	1
fib(1)	Not called	1	Returned	Returned	Returned
fib(0)	Not called	0	Returned	Returned	Returned

Key Moments - 3 Insights

Why does fib(2) get computed twice in simple recursion?

Because recursion calls fib(2) separately from fib(3) and fib(4) without saving results, as shown in steps 6 and 12 in the execution table.

When should we choose dynamic programming over simple recursion?

When subproblems overlap and get recomputed multiple times, like fib(2) here, DP saves results to avoid repeated work, improving efficiency.

Why is greedy not suitable for Fibonacci calculation?

Because Fibonacci depends on previous two values (optimal substructure) but no greedy choice can build the solution step-by-step without missing subproblems.

Visual Quiz - 3 Questions

Look at the execution table, what is the result returned by fib(3) at step 8?

A 1

B 2

C 3

D Pending

💡 Hint

Check the 'Result Returned' column at step 8 in the execution table.

At which step does the call stack become empty, indicating all recursion calls finished?

A Step 10

B Step 12

C Step 13

D Step 6

💡 Hint

Look at the 'Visual State' column for when the call stack is empty.

If we use dynamic programming, how would the number of fib(2) computations change compared to this recursion?

A It would reduce to one

B It would increase

C It would stay the same

D It would be zero

💡 Hint

Refer to variable_tracker and key_moments about overlapping subproblems.

Concept Snapshot

DP vs Recursion vs Greedy:
- Recursion solves by calling itself, may recompute subproblems.
- DP saves results to avoid repeated work (overlapping subproblems).
- Greedy picks best local choice, works if problem has optimal substructure.
- Choose DP if subproblems overlap.
- Choose Greedy if local choices lead to global optimum.
- Choose Recursion if problem is simple or no overlap.

Full Transcript

This concept helps decide when to use recursion, dynamic programming, or greedy algorithms. Recursion solves problems by calling itself but can repeat work. Dynamic programming improves recursion by saving results of subproblems to avoid recomputation, especially when subproblems overlap. Greedy algorithms pick the best choice at each step and work when this leads to the best overall solution. The example of Fibonacci numbers shows simple recursion calling fib(2) twice, which wastes time. Dynamic programming would compute fib(2) once and reuse it. Greedy is not suitable here because Fibonacci depends on previous two values, not a single local choice. The execution table traces each recursive call and return, showing the call stack growing and shrinking. Variable tracker shows how values change after key steps. Key moments clarify why repeated computation happens and when to choose each method. The visual quiz tests understanding of the execution steps and concepts. This helps beginners see how these approaches differ and when to pick the right tool for a problem.