Table of Contents

Introduction to Recursion

Recursion occurs when a function calls itself to tackle smaller portions of the same problem.

In a recursive process, each call to the function is a step or iteration that works on a smaller piece of the problem, and the recursion proceeds until it reaches a base case.

The Factorial Function: A Classic Example

The factorial of a number, denoted by n!, is the product of all positive integers up to n. Notably, the factorial of 0 is defined as 1.

Factorials beautifully illustrate recursion because calculating n! inherently involves computing (n-1)!, (n-2)!, and so on, down to 0!.

Implementing Recursion in Java

To embody recursion in code, we require two key components: a base case and the recursion logic. The base case acts as a stop signal, preventing infinite recursion, while the logic addresses the smaller segments of the problem.

Coding the Factorial Function

We'll create a class named Factorial with a method calculateFactorial that calculates the factorial of a given number n.

public class Factorial {

    public int calculateFactorial(int n) {
        // Base case
        if (n == 0) {
            return 1;
        }

        // Recursive call
        return n * calculateFactorial(n - 1);
    }

    public static void main(String[] args) {
        Factorial fact = new Factorial();
        int n = 5; // Let's calculate 5!
        System.out.println("Factorial of " + n + " is: " + fact.calculateFactorial(n));

        // Testing with another value
        n = 10; // Now calculating 10!
        System.out.println("Factorial of " + n + " is: " + fact.calculateFactorial(n));
    }
}

In this example, calculateFactorial method demonstrates recursion. The function continually calls itself with n-1 until n equals 0, at which point it returns 1—satisfying the base case.

Understanding the Flow

For calculateFactorial(5), the process unfolds as follows:

1. 5 * calculateFactorial(4)
2. 4 * calculateFactorial(3)
3. 3 * calculateFactorial(2)
4. 2 * calculateFactorial(1)
5. 1 * calculateFactorial(0) (base case reached)