Factorial Using Recursion in DSA Javascript

Mental Model

A function calls itself with a smaller number until it reaches 1, then multiplies back up to get the factorial.

Analogy: Imagine stacking blocks: you keep adding one block on top of the smaller stack until you have one block, then count the total by multiplying the heights as you go back down.

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 to a smaller number to break it down

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

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

Why: Keep reducing until we reach the base case

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 x factorial(1) = 2 x 1 = 2

factorial(2) returns 2

Why: Multiply current number by result of smaller factorial

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

factorial(3) returns 6

Why: Multiply current number by result of smaller factorial

Result:

factorial(3) = 6

Annotated Code

DSA Javascript

function factorial(n) {
  if (n === 0 || n === 1) return 1; // base case stops recursion
  return n * factorial(n - 1); // recursive call with smaller number
}

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

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

stop recursion when n reaches 0 or 1

return n * factorial(n - 1);

call factorial with smaller number and multiply by current n

Output

factorial(3) = 6

Complexity Analysis

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

Space: O(n) because each recursive call adds a layer to the call stack

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to understand for factorial

Edge Cases

input is 1

returns 1 immediately as base case

DSA Javascript

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

input is 0

returns 1 immediately as base case

DSA Javascript

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

When to Use This Pattern

When you see a problem that can be broken into smaller identical problems, use recursion to solve by calling the same function with smaller inputs.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add a base case like if (n === 0 || n === 1) return 1 to stop recursion

Mistake: Not reducing the input in recursive call leads to infinite loop
Fix: Call factorial(n - 1) to reduce input each time

Summary

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

Use when a problem can be divided into smaller identical subproblems.

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 number multiplied by 2

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

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

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 with definition

   Only The product of all positive integers up to that number matches this definition exactly.

3. Final Answer:

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

4. Quick Check:

   Factorial = product sequence [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial doubles the number
• Mixing factorial with division

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

easy

A. if (n === 1) return n * factorial(n - 1);

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

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

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

Solution

1. Step 1: Identify base case for factorial

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

2. Step 2: Check options for correct base case

   if (n === 0) return 1; returns 1 when n is 0, which is correct. Others either return wrong values or recursive calls.

3. Final Answer:

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

4. Quick Check:

   Base case n=0 returns 1 [OK]

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

Common Mistakes:

• Returning 0 for factorial(0)
• Using recursive call in base case
• Confusing base case with recursive step

3. What will be the output of the following JavaScript code?

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

medium

A. 24

B. 10

C. 16

D. 120

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 A

4. Quick Check:

   4! = 24 [OK]

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

Common Mistakes:

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

4. Find the error in this recursive factorial function:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n + 1);
}

medium

A. The base case should be n === 0, not n === 1

B. The recursive call should use n - 1, not n + 1

C. The function should return n + factorial(n - 1)

D. There is no error; the function is correct

Solution

1. Step 1: Analyze recursive call direction

   The function calls factorial(n + 1), which increases n, causing infinite recursion.

2. Step 2: Correct recursive call

   To reach base case, n should decrease by 1 each call: factorial(n - 1).

3. Final Answer:

   The recursive call should use n - 1, not n + 1 -> Option B

4. Quick Check:

   Recursion must move toward base case [OK]

Hint: Recursive calls must reduce n to base case [OK]

Common Mistakes:

• Increasing n in recursive call
• Wrong base case value
• Using addition instead of multiplication

5. Consider this modified factorial function that returns the factorial of n only if n is even, otherwise returns 0:

function evenFactorial(n) {
  if (n === 0) return 1;
  if (n % 2 !== 0) return 0;
  return n * evenFactorial(n - 2);
}
console.log(evenFactorial(6));

What is the output of this code?

hard

A. 48

B. 720

C. 0

D. 120

Solution

1. Step 1: Understand function behavior

   Function returns 0 if n is odd. For even n, it multiplies n by factorial of n-2 recursively.

2. Step 2: Calculate evenFactorial(6)

   evenFactorial(6) = 6 * evenFactorial(4) evenFactorial(4) = 4 * evenFactorial(2) evenFactorial(2) = 2 * evenFactorial(0) evenFactorial(0) = 1 (base case) So, 2 * 1 = 2 4 * 2 = 8 6 * 8 = 48

3. Final Answer:

   48 -> Option A

4. Quick Check:

   Product of even numbers down to 0 = 48 [OK]

Hint: Multiply even numbers down by 2 recursively [OK]

Common Mistakes:

• Calculating full factorial instead of even factorial
• Returning 0 for even inputs
• Ignoring base case for 0