Умови виходу. 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);
    }
}
    

Висновок буде: