Recursion vs Iteration When Each Wins in DSA Typescript - Trade-offs & Analysis

Mental Model

Recursion solves problems by breaking them into smaller copies of the same problem, while iteration solves problems by repeating steps in a loop.

Analogy: Recursion is like a set of nested Russian dolls, where each doll contains a smaller one inside, and iteration is like walking around a track repeatedly until you finish.

Recursion:
  call1 -> call2 -> call3 -> base case
Iteration:
  start -> step -> step -> step -> end

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion and iteration

Goal: Show how recursion and iteration solve the same problem differently and when each is better

Step 1: Recursion calls factorial(4), which calls factorial(3)

factorial(4) -> factorial(3) ↑

Why: Recursion breaks the problem into smaller parts

Step 2: Recursion calls factorial(3), which calls factorial(2)

factorial(4) -> factorial(3) -> factorial(2) ↑

Why: Keep breaking down until base case

Step 3: Recursion calls factorial(2), which calls factorial(1)

factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Reach base case where factorial(1) = 1

Step 4: Recursion returns 1 for factorial(1), then factorial(2) = 2 * 1 = 2

returning: factorial(1)=1 -> factorial(2)=2

Why: Start combining results back up

Step 5: Recursion returns factorial(3) = 3 * 2 = 6

returning: factorial(3)=6

Why: Combine next level

Step 6: Recursion returns factorial(4) = 4 * 6 = 24

returning: factorial(4)=24

Why: Final result computed

Step 7: Iteration starts with result=1 and i=1, multiply result by i

result=1, i=1

Why: Initialize iteration

Step 8: Iteration multiply result=1 * 2=2, i=2

result=2, i=2

Why: Multiply step by step

Step 9: Iteration multiply result=2 * 3=6, i=3

result=6, i=3

Why: Continue multiplication

Step 10: Iteration multiply result=6 * 4=24, i=4

result=24, i=4

Why: Final multiplication

Result:

Recursion stack unwound: factorial(4) = 24
Iteration final result: 24

Annotated Code

DSA Typescript

class Factorial {
  // Recursive factorial function
  static factorialRecursive(n: number): number {
    if (n <= 1) return 1; // base case
    return n * Factorial.factorialRecursive(n - 1); // recursive call
  }

  // Iterative factorial function
  static factorialIterative(n: number): number {
    let result = 1;
    for (let i = 1; i <= n; i++) {
      result *= i; // multiply result by current i
    }
    return result;
  }
}

// Driver code
const n = 4;
console.log("Recursion factorial of", n, "=", Factorial.factorialRecursive(n));
console.log("Iteration factorial of", n, "=", Factorial.factorialIterative(n));

if (n <= 1) return 1; // base case

stop recursion when n is 1 or less

return n * Factorial.factorialRecursive(n - 1); // recursive call

call factorial for smaller n and multiply

for (let i = 1; i <= n; i++) { result *= i; }

multiply result by each number from 1 to n

Output

Recursion factorial of 4 = 24

Iteration factorial of 4 = 24

Complexity Analysis

Time: O(n) because both recursion and iteration multiply n numbers once

Space: Recursion uses O(n) space for call stack; iteration uses O(1) constant space

vs Alternative: Iteration is more space efficient since recursion uses extra stack memory; recursion can be simpler to write and understand for problems naturally defined recursively

Edge Cases

n = 0

Both recursion and iteration return 1 as factorial(0) = 1

DSA Typescript

if (n <= 1) return 1; // base case

n = 1

Both return 1 immediately without further calls or loops

DSA Typescript

if (n <= 1) return 1; // base case

negative n

Both return 1 immediately (recursion hits base case since n <= 1; iteration loop doesn't run), though factorial is undefined for negatives

DSA Typescript

if (n <= 1) return 1; // base case

When to Use This Pattern

When a problem naturally breaks into smaller similar problems, recursion is a good fit; when you want to save memory and avoid call stack overhead, iteration is better.

Common Mistakes

Mistake: Not defining a proper base case in recursion causing infinite calls
Fix: Add a base case like 'if (n <= 1) return 1' to stop recursion

Mistake: Using recursion for very large inputs causing stack overflow
Fix: Use iteration or tail recursion optimization if supported

Summary

Recursion solves problems by calling itself with smaller inputs; iteration uses loops to repeat steps.

Use recursion when the problem is naturally recursive and easier to express that way; use iteration when memory efficiency and speed matter.

The key insight is recursion uses the call stack to remember work, while iteration keeps track with variables and loops.