Recursion in Java

Recursion is a programming technique where a method calls itself to solve smaller instances of a problem. This approach is particularly useful for problems that can be divided into similar sub-problems, such as mathematical computations, data structure traversal, and more.

How Recursion Works

A recursive function has two main components:

1. Base Case: The condition under which the recursion stops. Without a base case, the function would call itself indefinitely, leading to a StackOverflowError.
2. Recursive Case: The part of the function where it calls itself to solve a smaller version of the problem.

Example: Factorial Calculation

The factorial of a number $$ n $$ is defined as $$ n! = n \times (n-1)! $$, with $$ 0! = 1 $$.

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

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

Output:

Factorial of 5 is: 120

Key Concepts in Recursion

1. Stack Memory Usage:
   • Each recursive call adds a new frame to the call stack.
   • When the base case is reached, the stack unwinds as each call completes.
2. Halting Condition:
   • A recursive function must have a condition to terminate; otherwise, it leads to infinite recursion.
3. Advantages:
   • Simplifies code for problems like tree traversal, backtracking, and divide-and-conquer algorithms.
   • Often more intuitive for problems with repetitive sub-problems.
4. Disadvantages:
   • Higher memory usage due to stack allocation.
   • Slower than iterative solutions in some cases due to overhead from repeated function calls.