Write A Java Program To Find Factorial Of A Positive Integer Number With Recursion

Calculating the factorial of a number is a fundamental concept in mathematics and computer science. It represents the product of all positive integers less than or equal to a given positive integer.

In this article, you will learn how to implement a Java program to calculate the factorial of a positive integer using recursion.

Problem Statement

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. A special case is 0!, which is defined as 1. Calculating factorials is a common problem in fields like combinatorics, probability, and algorithm analysis, often requiring an efficient and clear implementation.

Example

The factorial of 5 is 120. This is derived from multiplying 5 by all the positive integers less than it: 5 * 4 * 3 * 2 * 1.

Background & Knowledge Prerequisites

To understand this article, readers should have a basic understanding of:

• Java Fundamentals: Variables, data types, methods, and conditional statements (if-else).
• Recursion: The concept where a function calls itself directly or indirectly to solve a problem. A recursive solution typically involves a base case (the simplest form of the problem that can be solved directly) and a recursive step (where the function calls itself with a smaller input).

Use Cases or Case Studies

Factorials appear in various practical scenarios:

• Combinations and Permutations: Calculating the number of ways to arrange or select items from a set. For instance, the number of ways to arrange n distinct items is n!.
• Probability Theory: Used in probability distributions, such as the binomial distribution.
• Series Expansions: Factorials are fundamental in Taylor series expansions for functions like e^x or sin(x).
• Algorithm Analysis: Used to describe the time complexity of certain algorithms, particularly those involving permutations.
• Data Structures: Sometimes used in algorithms for tree traversals or graph theory problems.

Solution Approaches

For calculating factorials, the two most common approaches are iterative (using loops) and recursive (using self-calling functions). While iteration is often more memory-efficient, recursion provides an elegant and concise solution, especially for problems that naturally fit a recursive definition.

We will focus on the recursive approach.

Recursive Factorial Calculation

This approach defines the factorial function in terms of itself, leveraging the mathematical definition n! = n * (n-1)! with a base case 0! = 1.

// Factorial with Recursion
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {

    // Recursive method to calculate factorial
    public static long calculateFactorial(int n) {
        // Step 1: Define the base case
        // The factorial of 0 or 1 is 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // Step 2: Define the recursive step
        // n! = n * (n-1)!
        else {
            return n * calculateFactorial(n - 1);
        }
    }

    public static void main(String[] args) {
        // Step 1: Create a Scanner object to read user input
        Scanner scanner = new Scanner(System.in);

        // Step 2: Prompt the user to enter a non-negative integer
        System.out.print("Enter a non-negative integer: ");
        int number = scanner.nextInt();

        // Step 3: Validate the input to ensure it's non-negative
        if (number < 0) {
            System.out.println("Factorial is not defined for negative numbers.");
        } else {
            // Step 4: Calculate the factorial using the recursive method
            long factorialResult = calculateFactorial(number);

            // Step 5: Display the result
            System.out.println("The factorial of " + number + " is: " + factorialResult);
        }

        // Step 6: Close the scanner
        scanner.close();
    }
}

Run

Sample Output

Enter a non-negative integer: 5
The factorial of 5 is: 120

Enter a non-negative integer: 0
The factorial of 0 is: 1

Enter a non-negative integer: 1
The factorial of 1 is: 1

Stepwise Explanation

1. calculateFactorial(int n) Method:

• This method is responsible for computing the factorial recursively.
• Base Case: The if (n == 0 || n == 1) condition handles the simplest cases where the factorial is known directly (0! = 1, 1! = 1). This is crucial to stop the recursion and prevent infinite calls.
• Recursive Step: If n is greater than 1, the else block executes. It returns n * calculateFactorial(n - 1). This means to find n!, the method calls itself to find (n-1)! and then multiplies the result by n.

1. main Method:

• A Scanner object is initialized to read input from the console.
• The user is prompted to enter an integer.
• Input validation checks if the number is negative. Factorials are not typically defined for negative numbers in this context.
• If the input is valid, calculateFactorial() is called with the user's number.
• The returned factorial value is then printed to the console.
• The Scanner is closed to release system resources.

This recursive breakdown continues until the base case (0 or 1) is reached, at which point the values start returning up the call stack, multiplying at each step until the final result is obtained.

Conclusion

Recursion provides an elegant and intuitive way to solve problems that can be broken down into smaller, self-similar subproblems, such as calculating factorials. By defining a clear base case and a recursive step, we can write concise and readable code that mirrors the mathematical definition. While powerful, understanding the call stack and potential for stack overflow with very large inputs is important when using recursion.

Summary

• Factorial Definition: n! is the product of all positive integers up to n, with 0! = 1.
• Recursive Approach: Solves a problem by breaking it into smaller instances of the same problem.
• Base Case: Essential for terminating recursion (e.g., 0! = 1, 1! = 1).
• Recursive Step: Defines how the problem is reduced to a smaller instance (e.g., n! = n * (n-1)!).
• Java Implementation: A method that calls itself, incorporating the base and recursive steps.
• Use Cases: Found in combinatorics, probability, and algorithm analysis.