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.

Practice

1. What does the factorial of a number represent in mathematics?

easy

A. The product of all positive integers up to that number

B. The sum of all positive integers up to that number

C. The number multiplied by 2

D. The number divided by 2

Solution

1. Step 1: Understand factorial definition

   Factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

2. Step 2: Compare options

   Only the product of all positive integers up to that number correctly describes factorial as a product, not sum or other operations.

3. Final Answer:

   The product of all positive integers up to that number -> Option A

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial means multiply all numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides
• Mixing factorial with doubling

2. Which of the following is the correct base case for a recursive factorial function in TypeScript?

easy

A. if (n === 0) return 1;

B. if (n === 1) return 0;

C. if (n === 0) return 0;

D. if (n === 1) return n + 1;

Solution

1. Step 1: Identify factorial base case

   Factorial of 0 is defined as 1, so the base case should return 1 when n is 0.

2. Step 2: Check options

   Only if (n === 0) return 1; returns 1 when n is 0, which is correct base case for recursion.

3. Final Answer:

   if (n === 0) return 1; -> Option A

4. Quick Check:

   Base case: 0! = 1 [OK]

Hint: Base case for factorial is 0 returns 1 [OK]

Common Mistakes:

• Returning 0 for base case
• Using wrong base condition
• Returning n+1 incorrectly

3. What is the output of this TypeScript code?

function factorial(n: number): number {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 120

B. 10

C. 16

D. 24

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 * factorial(0) factorial(0) = 1 (base case)

2. Step 2: Calculate values bottom-up

   factorial(1) = 1 * 1 = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24

3. Final Answer:

   24 -> Option D

4. Quick Check:

   4! = 24 [OK]

Hint: Multiply down from n to 1 recursively [OK]

Common Mistakes:

• Stopping recursion too early
• Adding instead of multiplying
• Wrong base case

4. Identify the error in this recursive factorial function:

function factorial(n: number): number {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(0));

medium

A. No error, output is 1

B. Infinite recursion for input 0

C. Syntax error due to missing semicolon

D. Returns 0 for input 0

Solution

1. Step 1: Analyze base case for input 0

   Base case triggers only when n === 1, so factorial(0) calls factorial(-1), then factorial(-2), and so on infinitely.

2. Step 2: Understand recursion behavior

   Without base case for 0, recursion never stops for input 0, causing infinite recursion (stack overflow).

3. Final Answer:

   Infinite recursion for input 0 -> Option B

4. Quick Check:

   Missing base case for 0 causes infinite recursion [OK]

Hint: Always include base case for 0 in factorial [OK]

Common Mistakes:

• Missing base case for 0
• Assuming 1 covers 0
• Ignoring negative inputs

5. How can you modify the recursive factorial function to handle negative inputs gracefully in TypeScript?

hard

A. Return 0 for all negative inputs inside recursion

B. Remove the base case and let recursion handle negatives

C. Add a check to return -1 for negative inputs before recursion

D. Use a loop instead of recursion for negatives

Solution

1. Step 1: Understand factorial domain

   Factorial is not defined for negative numbers, so function should handle negatives before recursion.

2. Step 2: Add input validation

   Adding a condition to return -1 (or error) for negative inputs prevents invalid recursion calls.

3. Final Answer:

   Add a check to return -1 for negative inputs before recursion -> Option C

4. Quick Check:

   Validate input before recursion to handle negatives [OK]

Hint: Check negatives first, return error code [OK]

Common Mistakes:

• Ignoring negative inputs
• Letting recursion run on negatives
• Returning wrong values for negatives