Recursion Base Case and Recursive Case in DSA Typescript

Mental Model

Recursion solves a problem by breaking it into smaller parts until it reaches a simple case it knows how to solve directly.

Analogy: Imagine opening a set of nested Russian dolls: you keep opening smaller dolls until you find the smallest one that cannot be opened further, then you start putting them back together.

Problem -> Smaller Problem -> Smaller Problem -> Base Case (solved directly)
          ↑               ↑               ↑
       Recursive Case  Recursive Case  Base Case

Dry Run Walkthrough

Input: Calculate factorial of 3 (3!) using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down recursively

Step 1: Call factorial(3), not base case, so call factorial(2)

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

Why: We reduce the problem to a smaller one to solve step by step

Step 2: Call factorial(2), not base case, so call factorial(1)

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

Why: Keep breaking down until we reach the simplest case

Step 3: Call factorial(1), base case reached, return 1

factorial(1) = 1

Why: Base case stops recursion and provides a direct answer

Step 4: Return factorial(2) = 2 x factorial(1) = 2 x 1 = 2

factorial(2) = 2

Why: Combine smaller solved parts to build the answer

Step 5: Return factorial(3) = 3 x factorial(2) = 3 x 2 = 6

factorial(3) = 6

Why: Final answer is built by combining all parts

Result:

factorial(3) = 6

Annotated Code

DSA Typescript

class Recursion {
  static factorial(n: number): number {
    if (n === 0 || n === 1) {
      return 1; // base case: stop recursion
    }
    return n * Recursion.factorial(n - 1); // recursive case: reduce problem
  }
}

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

if (n === 0 || n === 1) { return 1; }

Check for base case to stop recursion and return direct answer

return n * Recursion.factorial(n - 1);

Recursive case: call factorial with smaller input to build solution

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 growing with each recursive call

vs Alternative: Iterative approach uses O(1) space but recursion is clearer for problems naturally defined by smaller subproblems

Edge Cases

Input is 1 (smallest factorial)

Returns 1 immediately as base case

DSA Typescript

if (n === 0 || n === 1) { return 1; }

Input is 0 (factorial of zero)

Returns 1 immediately as base case

DSA Typescript

if (n === 0 || n === 1) { return 1; }

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a simple stopping point, use recursion with base and recursive cases.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and stack overflow.
Fix: Always include a base case that stops recursion.

Mistake: Using incorrect base case value (e.g., n === 0 without handling) leads to errors.
Fix: Define base case carefully to cover smallest input correctly.

Summary

Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The base case stops recursion, and the recursive case breaks the problem down step by step.