Java Recursion [with Examples]

Summary: In this tutorial, you will learn about recursion in Java. You will also get to know about its advantages and disadvantages with the help of examples.

Recursion in Java

Recursion is a programming technique in which a method calls itself to solve a problem.

Recursion is useful for problems that can be broken down into smaller subproblems that are similar to the original problem.

In such cases, a recursive method can solve the smaller subproblems and then combine their solutions to solve the original problem.

Example 1: n^th term of Fibonacci Series using Recursion

For example, consider the problem of calculating the nth term of the Fibonacci sequence. The Fibonacci sequence is a series of numbers in which each number is the sum of the previous two numbers.

The first two numbers of the sequence are 0 and 1, and the rest of the sequence is calculated by adding the previous two numbers. The first few terms of the sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

The recursive method to calculate the nth term of the Fibonacci sequence could be written like this:

public int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This method works by first checking if n is 0 or 1. If it is, the method returns n without making any more recursive calls. If n is not 0 or 1, the method returns the sum of the Fibonacci numbers for n - 1 and n - 2.

This causes the method to call itself with n - 1 and n - 2, which are both smaller values of n.

The method will continue to call itself with smaller values of n until it reaches the base case, at which point it will begin returning values and unwinding the recursive calls.

To use this method, you would call it like this:

int result = fibonacci(10);

This would calculate the 10th term of the Fibonacci sequence, which is 34.

Example 2: Factorial of a number using Recursion

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

This method calculates the factorial of a number n, which is the product of all positive integers from 1 to n. For example, the factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120.

To use this method, you would call it like this:

int result = factorial(5);

The method works by first checking if n is 1. If it is, it returns 1, which is the base case of the recursion. If n is not 1, the method returns n multiplied by the factorial of n - 1.

This causes the method to call itself with a value that is one less than the original value of n.

The method will continue to call itself with decreasing values of n until it reaches the base case, at which point it will begin returning values and unwinding the recursive calls.

What is Base Case in Recursion?

In a recursive method, the base case is the point at which the recursion stops.

It is usually defined as a condition that is checked at the beginning of the method, and when it is met, the method returns a value without making any more recursive calls.

For example, in the factorial method I provided earlier, the base case is when n is equal to 1. When n is 1, the method returns 1 without making any more recursive calls. This is the base case because the factorial of 1 is always 1, and there is no need to continue making recursive calls.

The base case is important because it ensures that the recursion will eventually come to an end.

Without a base case, a recursive method could continue making recursive calls indefinitely, which would lead to an infinite loop.

Advantages and Disadvantages of Recursion

Advantages of recursion:

1. Recursive solutions can be very easy to read and understand, especially for problems that have a natural recursive structure.
2. Recursive solutions can be more elegant and concise than iterative solutions, as they can avoid the need for complex looping and state-tracking constructs.
3. Recursive solutions can be easier to write, as they often require fewer lines of code and less boilerplate than iterative solutions.

Disadvantages of recursion:

1. Recursive solutions can be more difficult to debug, as it can be hard to understand the flow of execution through multiple recursive calls.
2. Recursive solutions can be less efficient than iterative solutions, as they require the creation of new stack frames on the call stack for each recursive call. This can use up memory and CPU resources, especially for large input values or deeply nested recursive calls.
3. Recursive solutions can be prone to infinite loops if the base case is not properly defined or if there is a bug in the recursive logic.
4. Recursive solutions may not be suitable for problems that require a high degree of performance, as they may be slower and less efficient than iterative solutions.

Recursion can be a powerful tool for solving problems, but it is important to use it with caution, as it can also be easy to write recursive code that is inefficient or runs indefinitely.

---