Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Typescript - Why This Pattern

Mental Model

Recursion lets a function call itself to solve smaller parts of a problem, which loops can't do easily when the problem has many layers or branches.

Analogy: Imagine a set of nested boxes where each box contains a smaller box inside. To open all boxes, you open one box, then open the smaller box inside it, and so on. Loops can only open boxes one after another in a line, but recursion can open boxes inside boxes naturally.

Box1
 ↓
Box2
 ↓
Box3
 ↓
null

Recursion: function calls itself to open each box inside the previous one.

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Show how recursion breaks the problem into smaller parts and why loops struggle with this

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

factorial(3) -> factorial(2) -> ?

Why: We break the problem into smaller parts by calling the function itself with a smaller number

Step 2: factorial(2) calls factorial(1)

factorial(3) -> factorial(2) -> factorial(1) -> ?

Why: Keep breaking down until we reach the simplest case

Step 3: factorial(1) calls factorial(0), which returns 1 (base case)

factorial(3) -> factorial(2) -> factorial(1) -> factorial(0) = 1

Why: Base case stops recursion and starts returning values

Step 4: factorial(1) returns 1 * factorial(0) = 1

factorial(3) -> factorial(2) -> factorial(1) = 1

Why: Combine results going back up the call stack

Step 5: factorial(2) returns 2 * factorial(1) = 2

factorial(3) -> factorial(2) = 2

Why: Continue combining results

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

factorial(3) = 6

Why: Final result after all recursive calls complete

Result:

factorial(3) = 6

Annotated Code

DSA Typescript

class Factorial {
  static factorial(n: number): number {
    if (n === 0) return 1; // base case stops recursion
    return n * Factorial.factorial(n - 1); // recursive call with smaller problem
  }
}

// Driver code
const input = 3;
const result = Factorial.factorial(input);
console.log(`factorial(${input}) = ${result}`);

if (n === 0) return 1; // base case stops recursion

stop recursion when simplest case reached

return n * Factorial.factorial(n - 1); // recursive call with smaller problem

break problem into smaller part and combine results

Output

factorial(3) = 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) due to the call stack holding n recursive calls at once

vs Alternative: Loops can do repeated work but struggle to express problems that naturally break into smaller subproblems or nested layers without extra data structures

Edge Cases

input is 0

returns 1 immediately as base case

DSA Typescript

if (n === 0) return 1; // base case stops recursion

input is 1

calls factorial(0) then returns 1 * 1 = 1

DSA Typescript

return n * Factorial.factorial(n - 1); // recursive call with smaller problem

When to Use This Pattern

When a problem naturally breaks into smaller similar problems or nested layers, recursion is the right pattern because loops cannot express this nested breakdown cleanly.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion
Fix: Always include a base case that stops recursion

Mistake: Trying to convert recursive logic directly into a simple loop without extra data structures
Fix: Understand recursion handles nested or branching problems naturally, loops need extra work to do the same

Summary

Recursion solves problems by calling itself with smaller parts until reaching a simple base case.

Use recursion when problems have nested or branching structure that loops cannot express clearly.

The key insight is that recursion naturally handles nested layers by breaking problems down step-by-step.