Factorial Using Recursion in DSA Java - 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.

How many steps does the computer take when using recursion to find factorial?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code calculates the factorial of a number by calling itself with smaller numbers until it reaches zero.

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 reaching 0

How Execution Grows With Input

Each time we call factorial, it does one multiplication and calls itself with a smaller number until zero.

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

Pattern observation: The number of steps grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to calculate factorial grows in a straight line as the input number grows.

Common Mistake

[X] Wrong: "Recursion makes factorial calculation take much longer than a loop."

[OK] Correct: Both recursion and a loop do about the same number of steps here; recursion just calls itself instead of looping.

Interview Connect

Understanding how recursion grows with input helps you explain your code clearly and shows you know how to reason about performance.

Self-Check

"What if we used memoization to store results of factorial calls? 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 product of all positive integers up to that number

C. The sum 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 correctly describes factorial as a product, not sum or division.

3. Final Answer:

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

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides the number
• Assuming factorial doubles the number

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

easy

A. if (n == 1) return 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 factorial base case

   Factorial of 0 is defined as 1, so base case returns 1 when n == 0.

2. Step 2: Check options for correct base case

   Only if (n == 0) return 1; returns 1 when n == 0, others return incorrect values.

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 is n=0 returns 1 [OK]

Common Mistakes:

• Returning 0 for base case
• Using n==1 with wrong return value
• Missing base case causing infinite recursion

3. What is the output of the following Java code?

public class Main {
  public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
  }
  public static void main(String[] args) {
    System.out.println(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.

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
• Wrong base case causing wrong output
• Confusing factorial(4) with sum

4. Find the error in this recursive factorial function:

public static int factorial(int n) {
  if (n == 1) return 1;
  return n * factorial(n);
}

medium

A. Return type should be void

B. Missing base case for n == 0

C. Recursive call uses same n causing infinite recursion

D. Multiplication operator is incorrect

Solution

1. Step 1: Analyze recursive call parameter

   The function calls factorial(n) again without reducing n, causing infinite recursion.

2. Step 2: Identify correct recursive call

   Recursive call should be factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses same n causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive calls must reduce problem size [OK]

Common Mistakes:

• Calling factorial(n) instead of factorial(n-1)
• Missing base case for n=0
• Wrong return type

5. How would you modify the recursive factorial function to handle negative inputs by returning -1 for any negative number?

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}

hard

A. Add if (n < 0) return -1; before base case

B. Change base case to if (n <= 0) return 1;

C. Add if (n == 1) return -1; after base case

D. No change needed; factorial handles negatives

Solution

1. Step 1: Identify handling of negative inputs

   Factorial is undefined for negative numbers, so function should return -1 for n < 0.

2. Step 2: Add condition before base case

   Insert if (n < 0) return -1; before checking base case to catch negatives early.

3. Final Answer:

   Add if (n < 0) return -1; before base case -> Option A

4. Quick Check:

   Negative input returns -1 [OK]

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

Common Mistakes:

• Changing base case incorrectly
• Not handling negatives causing infinite recursion
• Assuming factorial works for negatives