Recursion

Recursion basics

A method can call another method. What is even more interesting, a method can call itself. This possibility is known as recursion and the method calling itself is named recursive method.

As a regular method, any recursive method can contain parameters and return something as well as it can take or return nothing.

The common idea of the recursion is the following: we have a method which solves a problem. It invokes itself inside the body (recursive call). Each recursive call solves a more simple problem that the previous call. For the simplest case, the result should be known. This way can be used to solve some problems instead of loops with iterations.

But how many times should a method call itself? It should be limited. The method must have a special condition to stop the recursion, otherwise, an error occurs.

So, every recursive method should have the following components:

• a trivial base case (one or more) to stop the recursion;
• a reduction step to obtain a more simple problem from the current problem.

To write recursive methods you should consider the solution of a problem as a smaller version of the same problem.

The factorial example

The classic example of the recursion is a math function calculating the factorial.

The factorial of a non-negative integer n is equal to the product of all positive integers from 1 to n inclusively.

For example, the factorial of 3 is 1 * 2 * 3 = 6.

We can say the factorial of n is equal to n multiplied by the factorial n - 1. Also, keep in mind, the factorial of 0 is 1 as well as the factorial of 1.

In accordance with the definition:

factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = ... = 4 * 3 * 2 * 1 = 24.

It's possible to write a method which does the same using the recursive call:

public static long factorial(long n) {
    if (n == 0 || n == 1) {
        return 1; // the trivial case
    } else {
        return n * factorial(n - 1); // the recursive call
    }
}

This method has one long parameter and returns a long result. The implementation includes:

• the trivial case that returns the value 1 without any recursive calls;
• the reduction step with the recursive call to simplify the problem.

We suppose, the passed argument >= 0. If the passed value is 0 or 1, the result is 1, otherwise, we invoke the same method decreasing the argument by one.

Let's invoke the method passing different arguments:

long fact0 = factorial(0); // 1 (by definition)
long fact1 = factorial(1); // 1
long fact2 = factorial(2); // 2 (1 * 2)
long fact3 = factorial(3); // 6 (1 * 2 * 3)
long fact4 = factorial(4); // 24 (1 * 2 * 3 * 4)

As you can see, it returns the expected results.

How does recursion work?

Each recursive call creates a new stack frame in the program stack. Each stack frame stores the run-time data of the executed method including values of local variables and the return value. When the trivial base case is reached, the method returns its value to the method by whom it's called.

Let's consider the same example with factorial to understand how the recursion work in the general case.

The lines below show the recursive calls for factorial(4).

factorial(4) returns 4 * factorial(3)
factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1

Once factorial(1) executes and returns 1 the value can be substituted back into the previous method call:

factorial(1) returns 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

So, factorial(4) returns 24.

But what happens if a recursive method never reaches a base case? The stack will never stop growing. If a program's stack exceeds the limit size, the StackOverflowError occurs. It will crash the program.

Replacing recursion by a loop

Every recursive method can be written iteratively using a loop.

Let's rewrite the factorial method in this way:

public static long factorial(long n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

You can be sure that the result will be the same.

Types of recursions

There are several types of recursions.

1) Direct recursion. A method invokes itself like the considered factorial method.

2) Indirect recursion. A method invokes another method that invokes the original method.

3) Tail-recursion. A call is tail-recursive if nothing has to be done after the call returns. I.e. when the call returns, the result is immediately returned from the calling method.

Other words, tail recursion is when the recursive call is the last statement in the method.

The considered recursive method for calculating factorial is not tail-recursion because after the recursive call it multiplies the result by a value. But it can be written as a tail recursive function. The general idea is to use an additional argument to accumulate the factorial value. When n reaches 0, the method should return the accumulated value.

public static long factorialTailRecursive(long n, long accum) {
    if (n == 0) {
        return accum;
    }
    return factorialTailRecursive(n - 1, n * accum);
}

And write a special wrapper to invoke it more convenient:

public static long factorial(long n) {
    return factorialTailRecursive(n, 1);
}

4) Multiple recursion. A method invokes itself recursively multiple times. The well-known example is calculating the N-th Fibonacci number using the recursion.

The recurrent formula:

Fib(n) = Fib(n - 1) + Fib(n - 2); Fib(0) = 0, Fib(1) = 1.

The Fibonacci sequence starts with: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

This solution is very inefficient, it's just an example of multiple recursion. Try to start the method passing 45 as the argument. It takes too much time. If you'll replace the recursion by a loop it will work much faster. Another possible optimization is the technique named memoization.

Recursion versus iterations

Recursion may provide a concise way to write code. Some problems are recursive by their nature.

Every recursive method can be written iteratively and vice versa. But as a rule, the recursive solution is slower than iterative and also takes an additional memory to store data in new stack frames.

Often, it's better to use loops in practice. But if you are sure that there will not be many recursive calls, you can use recursion as well.