Exit conditions. StackOverflowError

Example of recursive code without an exit condition

Let's take another look at a recursive problem. As an example, consider calculating Fibonacci numbers. Everybody will recall that the Fibonacci sequence is a numerical sequence in which the first two numbers are 0 and 1, and each subsequent number is equal to the sum of the two previous numbers.

Let's write code to calculate and display these numbers:

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}

Before the first call of the recursive printFibonacci method, print the first two numbers of the sequence: zero and one. We need to do this because the recursive method displays only the sum of the input parameters, not the parameters themselves.

The code looks okay: we get two numbers, calculate their sum, print it on the console, and call the printFibonacci method recursively again. We pass the previous number (previous) and the current number (current) as arguments.

Actually, the code has two errors. You can see them if you run the code.

The first error is overflowing the long type. The 104th number in our sequence is negative, indicating that the long type overflowed.

The second error is different. After calculating roughly 12,000 numbers, we get:

Now is an appropriate time to recall what a method call stack is in Java. The Java machine keeps a record of all function calls. To do this, it uses a special kind of collection called a stack. When one function calls another, the Java machine pushes a new StackTraceElement onto the stack. When the function ends, this element is removed from the stack. Accordingly, the stack always stores up-to-date information about the current state of the function call stack. The documentation for StackTraceElement says that it is "Thrown when a stack overflow occurs because an application recurses too deeply." A running JVM has a special area of memory for storing the method call stack. The size of this memory area depends on the OS and JVM settings. In addition to the method call stack itself, primitive variables (specific values of method parameters) and the addresses of reference variables (in a memory area called the "heap") are stored in this special memory area. Access to the call stack follows the LIFO principle.

Corrected example with an exit condition

Let's start by fixing the second problem in the code.

Let's try to solve the problem head-on: if the stack is too small, then let's make it bigger. To do this, start the JVM with the "-Xss" flag and specify how much memory to allocate for the stack. Let's try allocating 5 megabytes. This is what it will look like in IDEA:

We managed to increase the length of the output. Now can calculate more than 49,000 numbers of the sequence rather than being limited to about 12,000 numbers. But at some point, we still get a StackOverflowError.

You can try to increase the size of the stack, but that doesn't fix the fundamental problem. So, let's look for a problem in logic. There must be a point when the recursion stops. In other words, there must be some condition that determines when the recursive method will no longer be called, allowing the call stack to unwind. To define such a condition, let's make our objective explicit: display the Fibonacci series as long as its numbers are less than Integer.MAX_VALUE.

Let's write a new printFibonacciWithCondition method that will take this condition into account. And we will call the new corrected method in the main method.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}

After running the code, we see that the output ends with the number 1836311903. The number before this one is 1134903170. The sum of these numbers is 2_971_215_073, which is indeed greater than Integer.MAX_VALUE (2_147_483_647).

This change automatically fixed the long overflow bug. If you need to calculate more of the series, you will need to use other data types, such as BigInteger.

Recursive descent and unwinding

Let's analyze step by step how our code is executed. To do this, we'll add an echo method and call it before and after the recursive call of the printFibonacciWithCondition method.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}

The program gives us this output:

Here's a visualization of what is happening.

Let's say it again: the printFibonacciWithCondition method is called. It calculates the current number. If it suits us, then we display it and call the printFibonacciWithCondition method again with new arguments.

As long as the recursive method is being called, this is called "recursive descent". When recursive terminates and method calls return, we say that the call stack is "unwinding".

Recursion is an interesting topic in programming. To get a better handle on the material, let's change our task slightly. The new task is to output, in descending order, all numbers in the Fibonacci series that do not exceed Integer.MAX_VALUE. We've already written all the code needed for this task. All that remains is to swap the order of displaying the current number and calling the recursive method. That is, in the first example, the calculated number was displayed during the "descent", but now we need to "descend to the very bottom" and then display numbers "on the way back up". And of course, in the main method, we swap the two initial numbers of the sequence (zero and one) after display them after we call the recursive method. For readability, we omit the echo method.

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}

The output will be: