Factorial Using Recursion in DSA Java

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 by asking a friend to stack one less block until only one block is left, then stacking them back up together.

factorial(3)
  ↓ calls factorial(2)
    ↓ calls factorial(1)
      ↓ returns 1
    ← multiply 2 * 1 = 2
  ← multiply 3 * 2 = 6
result = 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 to factorial(2), multiply 2 * 1 = 2

factorial(2) returns 2

Why: Multiply current number by result of smaller factorial

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

factorial(3) returns 6

Why: Multiply current number by result of smaller factorial

Result:

6

Annotated Code

DSA Java

public class FactorialRecursion {
    // Recursive method to calculate factorial
    public static int factorial(int n) {
        if (n == 1) {
            return 1; // base case: factorial of 1 is 1
        }
        return n * factorial(n - 1); // recursive call with smaller number
    }

    public static void main(String[] args) {
        int number = 3;
        int result = factorial(number);
        System.out.println("Factorial of " + number + " is " + result);
    }
}

if (n == 1) {

check base case to stop recursion

return 1; // base case: factorial of 1 is 1

return 1 when base case reached

return n * factorial(n - 1);

recursive call multiplying current n by factorial of n-1

Output

Factorial of 3 is 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 O(1) space but recursion is simpler to write and understand

Edge Cases

Input is 1

Returns 1 immediately as base case

DSA Java

if (n == 1) {

Input is 0 (not handled in code)

Code does not handle 0, would cause infinite recursion

DSA Java

No guard for n == 0

When to Use This Pattern

When you see a problem that can be broken down into smaller versions of itself, use recursion to solve it step by step.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add a condition to stop recursion when n equals 1

Summary

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

Use when a problem naturally breaks down into smaller identical problems.

The key is the base case that stops recursion and starts returning results.

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