Почему моя рекурсия в Java не приводит к StackOverflowError?

Question

Для тестирования StackOverflowError в Java я написал следующий код:

package recursion_still_not_working;

public class Main {
    public static void main(String[] args) {
        // System.out.println(fibonacci(50));
        System.out.println("Result: " + factorial(3000));
    }

    public static long fibonacci(long n) {
        if (n > 1) {
            //System.out.println("calculating with " + (n - 1) + " + " + (n - 2));
            return  fibonacci(n - 1) + fibonacci(n - 2);
        } else {
            return n;
        }
    }

    public static long factorial(long n) {
        if (n > 1) {
            System.out.println("calculating with " + n);
            return n * factorial(n - 1);
        }
        System.out.println("base case reached: " + n);
        return n;
    }
}

Однако только factorial приводит к StackOverflowError, в то время как fibonacci проходит.Я думаю, что может происходить некоторая скрытая оптимизация моей JVM, которая принимает случай fibonacci, но не случай factorial.

Чем можно объяснить такое поведение?Для ясности: я ожидаю, что переполнение стека произойдет, но не происходит в одном из двух случаев, что меня смущает.Я не удивлен переполнением стека, которое действительно происходит.

Моя JVM:

openjdk 11.0.3 2019-04-16
OpenJDK Runtime Environment (build 11.0.3+7-Ubuntu-1ubuntu218.04.1)
OpenJDK 64-Bit Server VM (build 11.0.3+7-Ubuntu-1ubuntu218.04.1, mixed mode, sharing)

Answer 1

Саморекурсивный метод в Java вызовет StackOverflowError, если

 nos_levels * frame_size + overhead > stack_size

, где

• nos_levels - глубина рекурсии, необходимая для задачи
• frame_size - это размер (в байтах) кадра стека для рекурсивного метода,
• overhead представляет использование стека (в байтах) методов, которые запускают рекурсивное вычисление (например, вашmain method, etcetera)
• stack_size - размер стека (в байтах).

Теперь вы реализовали рекурсивные версии факториала и фибонации.Обе версии вернутся на глубину 3000 для расчета fibonacci(3000) или factorial(3000).И оба будут использовать стек одинакового размера и иметь одинаковые накладные расходы.

Разница, объясняющая, почему один сбой, а другой нет, заключается в размере кадра стека.

Теперь кадр стека обычно содержит следующее:

• указатель кадра, который указывает на кадр стека для родительского метода
• адрес возврата
• параметры метода
• объявленные локальные переменные метода
• любые неназванные временные переменные, необходимые для хранения промежуточных значений.

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

Очевидно, что ваши функции достаточно различны, поэтому им нужны стеки разного размера.Я не проверял это, но подозреваю, что это println заявления, которые делают это.Или, более конкретно, дополнительные скрытые переменные, необходимые для хранения промежуточных переменных, используемых при конкатенации строковых аргументов.

Если вы хотите быть уверенными, вам нужно взглянуть на код, генерируемый JIT-компилятором.

Answer 2

Исключение переполнения стека возникает, когда стек заполнен.Таким образом, вы неоднократно вызывали функции внутри функции, чтобы вызвать эту ситуацию.

В fibonacci (50) вызов не получает такую ​​большую глубину вызова.Глубина вызова fibinacci (n) составляет около n только.Но это занимает так много времени, потому что каждый вызов должен выполнить 2 вызова, поэтому вы получите 2 ^ n вызовов, которые должны быть выполнены.Но 2 вызова выполняются один за другим, поэтому они не добавляют оба к глубине стека.

Таким образом, чтобы попасть в исключение переполнения стека, вы должны: - выбрать достаточно высокое значение в качестве параметра - установить размерстека

Таким образом, вы можете легко использовать 3000 в качестве аргумента и, когда вы его вызываете, возможно, используйте -Xss256k, чтобы установить размер стека 256K.