Recursion in Java (or any programming language) is when a method (function) calls itself to solve a problem. This technique is useful for problems that can be broken down into smaller, similar problems. Each time the method calls itself, it works on a smaller part of the task, until it reaches a condition that stops it from calling itself anymore. This stopping point is called the base case.

Here’s how recursion works step-by-step:

1. Define the Base Case: This is the simplest version of the problem. When the method reaches the base case, it stops calling itself. Without a base case, the method would keep calling itself forever, causing an error.

2. Define the Recursive Case: This is the part where the method calls itself with a smaller or simpler version of the original problem.

Example: Factorial

A common example of recursion is calculating the factorial of a number. The factorial of a number $n$ (written as $n!$) is the product of all positive integers from $1$ to $n$.

For example:

• $3! = 3 \times 2 \times 1 = 6$
• $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

We can define factorial recursively because:

• $0! = 1$ (this is the base case)
• $n! = n \times (n - 1)!$

Here’s the Java code for calculating a factorial using recursion:

public class Factorial {
    public static int factorial(int n) {
        // Base case: if n is 0, return 1
        if (n == 0) {
            return 1;
        }
        // Recursive case: n * factorial(n - 1)
        return n * factorial(n - 1);
    }

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

How This Code Works

1. Base Case: When n is 0, the method returns 1.
2. Recursive Case: When n is not 0, the method calls itself with n - 1 and multiplies n by the result of factorial(n - 1).

So, for factorial(5), it will break down like this:

• factorial(5) calls factorial(4)
• factorial(4) calls factorial(3)
• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1)
• factorial(1) calls factorial(0), which returns 1 (base case)

Then, it calculates back up:

• factorial(1) = 1 * 1 = 1
• factorial(2) = 2 * 1 = 2
• factorial(3) = 3 * 2 = 6
• factorial(4) = 4 * 6 = 24
• factorial(5) = 5 * 24 = 120

Key Points

• Recursion is helpful for breaking down problems into simpler sub-problems.
• Always define a base case to prevent infinite loops.
• Recursive methods can be shorter and clearer but use more memory, so they’re not always the best choice for large problems.