Условия выхода из рекурсии. StackOverflowError

Пример кода на рекурсию без условия выхода

Давайте еще раз посмотрим на рекурсивную задачу. В качестве примера можно рассмотреть поиск чисел Фибоначчи. Кто не помнит, последовательность Фибоначчи – элементы числовой последовательности, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

Напишем код для поиска и вывода таких чисел:

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);
    }
}
    

Перед первым вызовом рекурсивного метода printFibonacci, выведем первые два числа последовательности – ноль и единицу. Это нужно, потому что в рекурсивном методе мы выводим только сумму полученных параметров, а не сами параметры.

Выглядит ОК: получаем два числа, считаем их сумму, выводим ее в консоль, и снова вызываем рекурсивный метод printFibonacci. В качестве параметров передаем предыдущее (previous) и текущее число (current).

На самом деле в этом коде есть 2 ошибки. Их можно заметить, если запустить код.

Первая ошибка заключается в переполнении типа long. Уже 104-е число в нашей последовательности вывелось отрицательным, а это значит, что произошло переполнение типа long.

Вторая ошибка имеет другой характер. После найденного 12 тысяч с копейками числа, на экран выводится:

Здесь уместно вспомнить, что такое стек вызова методов в Java. Java-машина ведет запись всех вызовов функций. У нее есть для этого специальная коллекция – стек (Stack). Когда одна функция вызывает другую, Java-машина помещает в этот стек новый элемент StackTraceElement. Когда функция завершается, этот элемент удаляется из стека. Таким образом в этом стеке всегда хранится актуальная информация о текущем состоянии "стека вызовов функций". Дословный перевод ошибки StackOverflowError – "стек переполнен". В Javadoc-е написано: "Бросается, когда стек вызова слишком глубокий". В запущенной JVM есть специальная область памяти для хранения стека вызова методов. Размер этой области памяти зависит от ОС и настроек JVM. Кроме самого стека вызовов методов в этой области памяти хранятся примитивные переменные (конкретные значения параметров вызова метода) и адреса ссылочных переменных (в HEAP области памяти). Модель доступа к стеку – LIFO.

Исправленный пример с условием выхода

Исправления нашего кода начнем со второй проблемы.

Попробуем проблему решить в лоб: если маленький размер стека, то давайте его увеличим. Для этого нужно запустить JVM со специальным флагом "-Xss" и указать сколько выделить памяти под стек. Давай попробуем выделить 5 мегабайт. Выглядеть это в IDEA будет так:

Да, длина вывода увеличилась и сейчас составляет не 12+ тысяч найденных чисел последовательности, а 49+ тысяч. Но после какого-то числа все равно получаем StackOverflowError.

Можно пробовать еще увеличивать стек-область памяти, но принципиально ничего не изменится. Значит, будем искать проблему в логике. У рекурсии должна быть точка остановки. То есть должно быть какое-то условие, после которого рекурсивный метод не вызовется, и стек вызова будет возвращаться. Для того, чтобы определить такое условие, давайте конкретизируем задачу – выводить числовой ряд Фибоначчи до тех пор, пока они меньше, чем Integer.MAX_VALUE.

Напишем новый метод printFibonacciWithCondition, в котором учтем это условие. И в методе main вызовем именно новый исправленный метод.

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);
    }
}
    

После запуска кода действительно видим, что вывод завершился числом 1836311903. Перед этим числом было 1134903170. Их сумма 2_971_215_073, что действительно больше Integer.MAX_VALUE (2_147_483_647).

Вместе с этим исправлением у нас автоматически исправилась ошибка с переполнением типа long. Если нужен более длинный числовой ряд, нужно использовать другие типы данных, например BigInteger.

Метод рекурсивного спуска и возврата

Давайте попробуем поэтапно проанализировать как выполняется наш код. Для это добавим метод echo и будем его вызывать перед и после рекурсивного вызова метода printFibonacciWithCondition.

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);
        }
    }
}
    

В результате работы программы получим вывод:

Давайте графически проиллюстрируем, как это происходит.

Проговорим еще раз: вызывается метод printFibonacciWithCondition. В нем вычисляется текущее число. Если оно подходит нам, то выводим его и снова вызываем метод printFibonacciWithCondition с новыми параметрами.

Пока идет вызов рекурсивного метода – это называется "Рекурсивный спуск". Когда идет возврат по стеку вызова – "Рекурсивный возврат".

Рекурсия – интересная тема в программировании. Для лучшего усвоения материала немного изменим нашу задачу. Нужно вывести ряд чисел Фибоначчи, которые не превышают Integer.MAX_VALUE в убывающем порядке. Для того, чтоб решить эту задачу, у нас уже написан весь код. Все что остается – это поменять местами вывод текущего числа и вызов рекурсивного метода. То есть в первом примере вывод найденного числа происходил "на этапе спуска", а сейчас нам нужно "спуститься в самый низ" и выводить числа на этапе "возврата". Ну и конечно, в методе main вывод двух начальных чисел последовательности (ноль и единица) поменять местами и вывести после вызова рекурсивного метода. Для читаемости удалим метод echo.

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);
    }
}
    

Вывод будет: