Условия за излизане. StackOverflowError

Пример за рекурсивен code без condition за изход

Нека хвърлим нов поглед върху рекурсивен проблем. Като пример, помислете за изчисляване на числата на Фибоначи. Всеки ще си спомни, че редицата на Фибоначи е числова редица, в която първите две числа са 0 и 1, а всяко следващо число е равно на сумата от двете предходни числа.

Нека напишем code за изчисляване и показване на тези числа:

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) като аргументи.

Всъщност codeът има две грешки. Можете да ги видите, ако стартирате codeа.

Първата грешка е препълването на дългия тип. 104-тото число в нашата последователност е отрицателно, което показва, че дългият тип е препълнен.

Втората грешка е различна. След като пресмятаме приблизително 12 000 числа, получаваме:

Сега е подходящ момент да си припомним Howво е стек за извикване на метод в Java. Java машината поддържа запис на всички извиквания на функции. За да направи това, той използва специален вид колекция, наречена стек. Когато една функция извиква друга, Java машината избутва нов StackTraceElement в стека. Когато функцията приключи, този елемент се премахва от стека. Съответно, стекът винаги съхранява актуална информация за текущото състояние на стека за извикване на функции. В documentацията за StackTraceElement се казва, че той е „Изхвърлен, когато възникне препълване на стека, защото приложение рекурсира твърде дълбоко“. Работеща JVM има специална област от паметта за съхраняване на стека за извикване на метод. Размерът на тази област на паметта зависи от настройките на операционната система и JVM. В допълнение към самия стек за извикване на метод, примитивните променливи (специфични стойности на параметрите на метода) и addressите на референтните променливи (в област на паметта, наречена "купчина") се съхраняват в тази специална област на паметта. Достъпът до стека за повиквания следва принципа LIFO.

Коригиран пример с condition за изход

Нека започнем с коригиране на втория проблем в codeа.

Нека се опитаме да решим проблема директно: ако стекът е твърде малък, нека го направим по-голям. За да направите това, стартирайте JVM с флага "-Xss" и укажете колко памет да разпределите за стека. Нека опитаме да разпределим 5 мегаbyteа. Ето How ще изглежда в IDEA:

Успяхме да увеличим дължината на изхода. Сега може да изчисли повече от 49 000 числа от последователността, instead of да бъде ограничен до около 12 000 числа. Но в няHowъв момент все още получаваме StackOverflowError .

Можете да опитате да увеличите размера на стека, но това не решава основния проблем. И така, нека потърсим проблем в логиката. Трябва да има момент, когато рекурсията спира. С други думи, трябва да има няHowво condition, което определя кога рекурсивният метод вече няма да бъде извикан, позволявайки на стека на повикванията да се отвие. За да дефинираме такова condition, нека изясним нашата цел: показване на реда на Фибоначи, стига числата му да са по-малки от Integer.MAX_VALUE .

Нека напишем нов метод printFibonacciWithCondition , който ще вземе предвид това condition. И ще извикаме новия коригиран метод в основния метод.

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

След изпълнение на codeа виждаме, че изходът завършва с числото 1836311903. Числото преди това е 1134903170. Сумата от тези числа е 2_971_215_073, което наистина е по-голямо от Integer.MAX_VALUE (2_147_483_647 ) .

Тази промяна автоматично поправи грешката с дългото препълване. Ако трябва да изчислите повече от сериите, ще трябва да използвате други типове данни, като BigInteger .

Рекурсивно спускане и размотаване

Нека да анализираме стъпка по стъпка How се изпълнява нашият code. За да направим това, ще добавим ехо метод и ще го извикаме преди и след рекурсивното извикване на метода 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 . Вече сме написали целия code, необходим за тази задача. Остава само да смените реда на показване на текущия номер и извикване на рекурсивния метод. Тоест в първия пример изчисленото число беше показано по време на „слизането“, но сега трябва да „слезем до самото дъно“ и след това да покажем числа „по пътя обратно нагоре“. И, разбира се, в основния метод разменяме двете начални числа на последователността (нула и едно), след като ги покажем, след като извикаме рекурсивния метод. За четливост,метод.

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

Резултатът ще бъде: