Factorial Using Recursion in DSA Javascript - Time & Space Complexity

Time Complexity: Factorial Using Recursion

O(n)

Understanding Time Complexity

We want to understand how the time needed to calculate a factorial grows as the input number gets bigger.

Specifically, how many steps does the recursive factorial function take as the input increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code calculates the factorial of a number using recursion by multiplying n with factorial of n-1 until it reaches 0.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call to factorial with n-1
• How many times: Exactly n times until base case n=0 is reached

How Execution Grows With Input

Each increase in input n adds one more recursive call, so the steps grow directly with n.

Input Size (n)	Approx. Operations
10	About 10 calls
100	About 100 calls
1000	About 1000 calls

Pattern observation: The number of steps grows in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute factorial grows linearly with the input number.

Common Mistake

[X] Wrong: "Recursion makes factorial calculation take exponential time because it calls itself repeatedly."

[OK] Correct: Each recursive call reduces n by 1 and only happens once per call, so calls grow linearly, not exponentially.

Interview Connect

Understanding recursion time helps you explain how functions work step-by-step and shows you can analyze code efficiency clearly.

Self-Check

"What if we changed the recursion to use memoization? How would the time complexity change?"

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