Factorial Using Recursion in DSA Java - Build from Scratch

Factorial Using Recursion

📖 Scenario: Imagine you are building a simple calculator app that can find the factorial of a number. Factorial means multiplying a number by all the numbers below it down to 1. For example, 4 factorial (written as 4!) is 4 x 3 x 2 x 1 = 24.

🎯 Goal: You will create a Java program that calculates the factorial of a number using a method that calls itself, called recursion. This helps you understand how problems can be solved by breaking them down into smaller parts.

📋 What You'll Learn

Create a method called factorial that takes an integer n and returns the factorial of n using recursion.

Use a base case in the factorial method to stop the recursion when n is 0.

Call the factorial method from the main method with the number 5.

Print the result of the factorial calculation.

💡 Why This Matters

🌍 Real World

Calculating factorials is useful in math problems, probability, and computer science algorithms like permutations and combinations.

💼 Career

Understanding recursion is important for software development roles, especially in algorithm design and problem solving.

1

Create the main class and main method

Create a public class called FactorialCalculator and inside it, create the main method with the exact signature public static void main(String[] args).

DSA Java

public class FactorialCalculator {
    public static void main(String[] args) {
        // Your code here
    }
}

Hint

Start by writing the class and main method exactly as shown. This is the basic structure of a Java program.

2

Add the recursive factorial method

Inside the FactorialCalculator class but outside the main method, create a public static method called factorial that takes an integer parameter n and returns an integer. Implement the base case: if n is 0, return 1.

DSA Java

public class FactorialCalculator {
    public static void main(String[] args) {
        
    }

    // Your code here
}

Hint

The base case stops the recursion. When n is 0, factorial is 1.

3

Complete the recursive call in factorial method

In the factorial method, after the base case, return n multiplied by the result of calling factorial with n - 1.

DSA Java

public class FactorialCalculator {
    public static void main(String[] args) {
        
    }

    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        }
        // Your code here
    }
}

Hint

This line makes the method call itself with a smaller number, building the factorial step by step.

4

Call factorial method and print the result

Inside the main method, call the factorial method with the number 5 and store the result in an integer variable called result. Then print result using System.out.println.

DSA Java

public class FactorialCalculator {
    public static void main(String[] args) {
        // Your code here
    }

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

Hint

Factorial of 5 is 120. Make sure to print the result variable.

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