DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Trade-offs & Analysis

Mental Model

We solve problems by breaking them down into smaller parts. Recursion tries all ways, greedy picks the best now, and DP remembers past results to avoid repeats.

Analogy: Imagine climbing stairs: recursion tries every path, greedy picks the next step that looks easiest, and DP remembers which steps are best to avoid climbing the same stairs again.

Recursion Tree:
    root
   /    \
  ...    ...

Greedy Path:
start -> best step -> next best -> ... -> end

DP Table:
Index: 0 1 2 3 4
Value: x x x x x
Memo:  x x x x x

Dry Run Walkthrough

Input: Problem: Find minimum cost to climb stairs with costs [10, 15, 20]

Goal: Compare how recursion, greedy, and DP solve this problem

Step 1: Recursion tries climbing from step 0: cost 10 + recurse from step 1

Recursion tree starts at step 0
Costs: 10 + ?

Why: Recursion explores all paths to find minimum cost

Step 2: Recursion tries climbing from step 1: cost 15 + recurse from step 2

Recursion tree at step 1
Costs: 15 + ?

Why: Recursion continues exploring all options

Step 3: Recursion tries climbing from step 2: cost 20 + recurse from step 3 (end)

Recursion tree at step 2
Costs: 20 + 0

Why: Reached end, base case returns 0

Step 4: Greedy picks step 0 cost 10, then step 1 cost 15, then step 2 cost 20, total 45

Greedy path: 10 -> 15 -> 20 = 45

Why: Greedy picks the cheapest immediate step

Step 5: DP fills memo: cost at step 2 is 20, step 1 is min(15+0, 15+20)=15, step 0 is min(10+15, 10+20)=25

DP memo: [25, 15, 20]

Why: DP remembers best cost from each step to avoid repeats

Step 6: DP returns minimum cost 25 starting from step 0

Final answer: 25

Why: DP finds optimal solution efficiently

Result:

DP memo: [25, 15, 20]
Minimum cost to climb stairs: 25

Annotated Code

DSA Typescript

class StairClimber {
  costs: number[];
  memo: number[];

  constructor(costs: number[]) {
    this.costs = costs;
    this.memo = Array(costs.length).fill(-1);
  }

  // Recursion: tries all paths
  minCostRecursion(step: number): number {
    if (step >= this.costs.length) return 0; // base case
    const costOneStep = this.costs[step] + this.minCostRecursion(step + 1); // step 1
    const costTwoSteps = this.costs[step] + this.minCostRecursion(step + 2); // step 2
    return Math.min(costOneStep, costTwoSteps);
  }

  // Greedy: picks cheapest immediate step
  minCostGreedy(): number {
    let total = 0;
    let i = 0;
    while (i < this.costs.length) {
      total += this.costs[i];
      if (i + 1 < this.costs.length && this.costs[i + 1] < (this.costs[i + 2] || Infinity)) {
        i += 1;
      } else {
        i += 2;
      }
    }
    return total;
  }

  // DP: remembers best cost from each step
  minCostDP(step: number): number {
    if (step >= this.costs.length) return 0; // base case
    if (this.memo[step] !== -1) return this.memo[step]; // return cached
    const costOneStep = this.costs[step] + this.minCostDP(step + 1);
    const costTwoSteps = this.costs[step] + this.minCostDP(step + 2);
    this.memo[step] = Math.min(costOneStep, costTwoSteps);
    return this.memo[step];
  }
}

// Driver code
const costs = [10, 15, 20];
const climber = new StairClimber(costs);
console.log("Recursion minimum cost:", climber.minCostRecursion(0));
console.log("Greedy minimum cost:", climber.minCostGreedy());
console.log("DP minimum cost:", climber.minCostDP(0));

if (step >= this.costs.length) return 0; // base case

stop recursion when past last step

const costOneStep = this.costs[step] + this.minCostRecursion(step + 1);

try taking one step forward

const costTwoSteps = this.costs[step] + this.minCostRecursion(step + 2);

try taking two steps forward

return Math.min(costOneStep, costTwoSteps);

choose cheaper path

while (i < this.costs.length) { total += this.costs[i]; ... }

sum costs by greedy choice

if (i + 1 < this.costs.length && this.costs[i + 1] < (this.costs[i + 2] || Infinity)) { i += 1; } else { i += 2; }

pick next step with smaller cost

if (this.memo[step] !== -1) return this.memo[step];

return cached result to avoid recomputation

this.memo[step] = Math.min(costOneStep, costTwoSteps);

store best cost for current step

Output

Recursion minimum cost: 25

Greedy minimum cost: 45

DP minimum cost: 25

Complexity Analysis

Time: Recursion: O(2^n) because it tries all paths; Greedy: O(n) because it picks steps once; DP: O(n) because it computes each step once and reuses results

Space: Recursion: O(n) due to call stack; Greedy: O(1) constant space; DP: O(n) for memo array

vs Alternative: DP is better than recursion because it avoids repeated work; greedy is fastest but can give wrong answers if problem needs global view

Edge Cases

Empty cost array

All methods return 0 cost

DSA Typescript

if (step >= this.costs.length) return 0; // base case

Single step cost array

Methods return cost of that single step

DSA Typescript

if (step >= this.costs.length) return 0; // base case

Costs with equal values

DP and recursion find correct minimum; greedy may pick suboptimal path

DSA Typescript

return Math.min(costOneStep, costTwoSteps);

When to Use This Pattern

When a problem asks for an optimal solution with overlapping subproblems, consider DP; if it can be solved by making local best choices, try greedy; if unsure, recursion helps explore all options.

Common Mistakes

Mistake: Using greedy when problem requires global optimization, leading to wrong answers
Fix: Check if problem has overlapping subproblems and optimal substructure; if yes, use DP

Mistake: Not caching results in recursion causing exponential time
Fix: Add memoization to store and reuse results

Summary

Recursion tries all possibilities, greedy picks local best, and DP remembers past results to avoid repeats.

Use recursion to explore, greedy when local choices guarantee global best, and DP when subproblems overlap.

The key is recognizing if the problem has overlapping subproblems and optimal substructure to pick DP over greedy or recursion.