StackOverFlowError при использовании рекурсии на SplayTree [дубликат]

A StackOverflowError - ошибка времени выполнения в java.

Он вызывается, когда количество памяти стека вызовов распределено JVM.

Обычный случай, когда a StackOverflowError выбрасывается, когда стек вызовов превышает из-за чрезмерной глубокой или бесконечной рекурсии.

Пример:

public class Factorial {
    public static int factorial(int n){
        if(n == 1){
            return 1;
        }
        else{
            return n * factorial(n-1);
        }
    }

    public static void main(String[] args){
        System.out.println("Main method started");
        int result = Factorial.factorial(-1);
        System.out.println("Factorial ==>"+result);
        System.out.println("Main method ended");
    }
}

Трассировка стека:

Main method started
Exception in thread "main" java.lang.StackOverflowError
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)

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

Переполнение стека означает, что: переполнение стека. Обычно в программе есть один стек, который содержит переменные и адреса локальной области, куда возвращаться, когда заканчивается выполнение подпрограммы. Этот стек имеет тенденцию быть фиксированным диапазоном памяти где-то в памяти, поэтому он ограничен, насколько он может содержать значения.

Если стек пуст, вы не можете поп, если вы получите стек ошибка переполнения.

Если стек заполнен, вы не можете нажать, если вы получите ошибку переполнения стека.

Таким образом, переполнение стека появляется там, где вы слишком много выделяете стек. Например, в упомянутой рекурсии.

Некоторые реализации оптимизируют некоторые формы рекурсий. Рекурсия хвоста в частности. Рекурсивные подпрограммы хвоста - это форма подпрограмм, в которых рекурсивный вызов появляется как последняя вещь, что делает процедура. Такой рутинный вызов просто сводится к прыжку.

Некоторые реализации заходят так далеко, что реализуют свои собственные стеки для рекурсии, поэтому они позволяют рекурсии продолжать, пока система не исчерпает память.

Самая простая вещь, которую вы могли бы попробовать, это увеличить размер стека, если сможете. Если вы не можете этого сделать, вторая лучшая вещь - посмотреть, есть ли что-то, что явно вызывает переполнение стека. Попробуйте, напечатав что-то до и после вызова в рутину. Это поможет вам узнать провал.

Как вы говорите, вам нужно показать код. : -)

Ошибка переполнения стека обычно происходит, когда ваша функция вызывает слишком много гнезд. См. Поток «Переполнение потока стека» для некоторых примеров того, как это происходит (хотя в случае этого вопроса ответы преднамеренно вызывают переполнение стека).

Переполнение стека обычно вызывается вызовом функций вложенности слишком глубоко (особенно просто при использовании рекурсии, то есть функции, которая вызывает себя) или выделения большого объема памяти в стеке, где использование кучи было бы более подходящим.

Чтобы описать это, сначала давайте понять, как хранятся локальные переменные и объекты.

Локальная переменная хранится в стеке: [/g1]

Если вы посмотрели на изображении вы должны понимать, как все работает.

Когда вызов функции вызывается Java-приложением, стек стека выделяется в стеке вызовов. Фрейм стека содержит параметры вызываемого метода, его локальные параметры и обратный адрес метода. Адрес возврата обозначает точку выполнения, из которой выполнение программы должно продолжаться после возврата вызванного метода. Если нет места для нового стека кадров, то StackOverflowError вызывается виртуальной машиной Java (JVM).

Наиболее распространенным случаем, который может исчерпать стек Java-приложения, является рекурсия. В рекурсии метод запускается во время его выполнения. Рекурсия рассматривается как мощный метод программирования общего назначения, но ее следует использовать с осторожностью, чтобы избежать StackOverflowError.

Пример, показывающий StackOverflowError, показан ниже:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);

        if(num == 0)
            return;
        else
            recursivePrint(++num);
    }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

В этом примере мы определяем рекурсивный метод, называемый recursivePrint, который печатает целое число, а затем вызывает себя со следующим последовательным целым числом в качестве аргумента. Рекурсия заканчивается, пока мы не перейдем в 0 в качестве параметра. Однако в нашем примере мы передали параметр из 1 и его увеличивающих последователей, следовательно, рекурсия никогда не завершится.

Пример выполнения с использованием флага -Xss1M, который определяет размер стека потоков ниже 1MB, показано ниже:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

В зависимости от начальной конфигурации JVM результаты могут отличаться, но в конечном итоге следует вызывать StackOverflowError. Этот пример является очень хорошим примером того, как рекурсия может вызвать проблемы, если не выполнять их с осторожностью.

Как работать с StackOverflowError

1. Простейшим решением является тщательная проверка трассировки стека и обнаружение повторяющегося шаблона номеров строк. Эти номера строк указывают, что код рекурсивно называется. Как только вы обнаружите эти строки, вы должны тщательно проверить свой код и понять, почему рекурсия никогда не заканчивается.
2. Если вы подтвердили правильность реализации рекурсии, вы можете увеличить размер стека, чтобы разрешить большее количество вызовов. В зависимости от установленной виртуальной машины Java (JVM) размер стека по умолчанию может равняться либо 512 КБ, либо 1 МБ. Вы можете увеличить размер стека потоков, используя флаг -Xss. Этот флаг можно указать либо через конфигурацию проекта, либо через командную строку. Формат аргумента -Xss: -Xss<size>[g|G|m|M|k|K]

Вот пример

public static void main(String[] args) {
    System.out.println(add5(1));
}

public static int add5(int a) {
    return add5(a) + 5;
}

. StackOverflowError в основном - это когда вы пытаетесь что-то сделать, что, скорее всего, называет себя и продолжает бесконечность (или до тех пор, пока не даст StackOverflowError).

add5(a) будет вызывать себя, а затем снова называть себя и т. д.

Если у вас есть такая функция, как:

int foo()
{
    // more stuff
    foo();
}

Затем foo () будет продолжать называть себя, все глубже и глубже, и когда пространство, используемое для отслеживания того, какие функции вы используете, заполненный, вы получаете ошибку переполнения стека.

Часто используется термин «переполнение стека» (переполнение), но неправильное обозначение; атаки не переполняют стек, а буферы в стеке.

- из слайдов слайдов Prof. Доктор Дитер Голманн

Наиболее распространенной причиной переполнения стека является чрезмерно глубокая или бесконечная рекурсия. Если это ваша проблема, этот учебник о Java Recursion может помочь понять проблему.

Вот пример рекурсивного алгоритма для обращения к односвязному списку. На ноутбуке со следующей спецификацией (память 4G, процессор Intel Core i5 2.3GHz, 64-разрядная версия Windows 7) эта функция будет запущена с ошибкой StackOverflow для связанного списка размером около 10 000.

Могу сказать, что мы должны использовать рекурсию разумно, всегда принимая во внимание масштаб системы. Часто рекурсия может быть преобразована в итеративную программу, которая масштабируется лучше. (Одна итеративная версия того же алгоритма приведена в нижней части страницы, она меняет один и тот же список размером 1 миллион за 9 миллисекунд.)

    private static LinkedListNode doReverseRecursively(LinkedListNode x, LinkedListNode first){

    LinkedListNode second = first.next;

    first.next = x;

    if(second != null){
        return doReverseRecursively(first, second);
    }else{
        return first;
    }
}

public static LinkedListNode reverseRecursively(LinkedListNode head){
    return doReverseRecursively(null, head);
}

Итеративная версия того же алгоритма:

    public static LinkedListNode reverseIteratively(LinkedListNode head){
    return doReverseIteratively(null, head);
}   

private static LinkedListNode doReverseIteratively(LinkedListNode x, LinkedListNode first) {

    while (first != null) {
        LinkedListNode second = first.next;
        first.next = x;
        x = first;

        if (second == null) {
            break;
        } else {
            first = second;
        }
    }
    return first;
}


public static LinkedListNode reverseIteratively(LinkedListNode head){
    return doReverseIteratively(null, head);
}