Factorial Using Recursion in DSA Typescript

Mental Model

A function calls itself with a smaller number until it reaches 1, then multiplies all those numbers back up.

Analogy: Imagine stacking blocks: you keep adding one block on top of the smaller stack until you reach the base block, then count all blocks by multiplying their heights.

factorial(3)
  ↓ calls factorial(2)
    ↓ calls factorial(1)
      ↓ returns 1
    ← returns 2 * 1 = 2
  ← returns 3 * 2 = 6

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 = 6 by recursive calls

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

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

Why: We reduce the problem by one to reach the base case

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

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

Why: Keep reducing until base case 1 is reached

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

factorial(1) returns 1

Why: Base case stops recursion and starts returning values

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

factorial(2) returns 2

Why: Multiply current number by result of smaller problem

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

factorial(3) returns 6

Why: Multiply current number by result of smaller problem to get final answer

Result:

factorial(3) = 6

Annotated Code

DSA Typescript

class Factorial {
  static factorial(n: number): number {
    if (n <= 1) {
      return 1; // base case: factorial of 1 or 0 is 1
    }
    return n * Factorial.factorial(n - 1); // recursive call with smaller number
  }
}

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

if (n <= 1) { return 1; }

stop recursion when n is 1 or less, return 1 as factorial base case

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

multiply current number by factorial of one less number

Output

factorial(3) = 6

Complexity Analysis

Time: O(n) because the function calls itself n times until it reaches 1

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

vs Alternative: Iterative approach uses a loop and constant space O(1), but recursion is simpler to understand for factorial

Edge Cases

n = 0

Returns 1 because factorial of 0 is defined as 1

DSA Typescript

if (n <= 1) { return 1; }

n = 1

Returns 1 immediately as base case

DSA Typescript

if (n <= 1) { return 1; }

n < 0 (negative number)

Function returns 1 due to base case but factorial is undefined for negatives; no error handling here

DSA Typescript

if (n <= 1) { return 1; }

When to Use This Pattern

When you see a problem that can be broken down into smaller versions of itself, like factorial, use recursion to solve it by calling the function inside itself.

Common Mistakes

Mistake: Missing the base case causes infinite recursion and crash
Fix: Always include a base case like 'if (n <= 1) return 1' to stop recursion

Mistake: Calling factorial(n + 1) instead of factorial(n - 1) leads to infinite calls
Fix: Call factorial with a smaller number 'n - 1' to move toward base case

Summary

Calculates factorial of a number by calling itself with smaller numbers until reaching 1.

Use recursion when a problem can be divided into smaller identical problems.

The key is the base case that stops recursion and the recursive call that reduces the problem size.