为什么我在 Java 中的递归不会导致 StackOverflowError？

Question

为了在Java中测试WhosebugError，我写了下面的代码：

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 导致 WhosebugError，而 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

Stack Overflow异常出现，当Stack满了。所以你在函数内部反复调用了一个函数才触发了这种情况。

在 fibonacci(50) 调用中没有获得如此高的调用深度。 fibinacci(n) 的调用深度只有 n 左右。但这需要很长时间，因为每次调用都必须进行 2 次调用，所以你最终必须完成 2^n 次调用。但是这 2 个调用是一个接一个地完成的，所以它们不会同时增加堆栈深度。

所以要进入堆栈溢出异常，你应该： - 选择足够高的值作为参数 - 设置堆栈的大小

因此您可以轻松地使用 3000 作为参数，当您调用它时，可以使用 -Xss256k 将堆栈大小设置为 256K。

Answer 2

Java 中的 self-recursive 方法将导致 WhosebugError 如果

 nos_levels * frame_size + overhead > stack_size

哪里

nos_levels是问题需要的递归深度
frame_size 是递归方法的堆栈帧的大小（以字节为单位），
overhead 表示启动递归计算的方法（例如您的 main 方法等）的堆栈使用情况（以字节为单位）
stack_size是栈的大小（以字节为单位）。

现在你已经实现了阶乘和斐波那契的递归版本。两个版本都会递归到3000的深度来计算fibonacci(3000)或者factorial(3000)。两者都将使用相同大小的堆栈，并且具有相同的开销。

解释为什么一个崩溃而另一个不崩溃的区别是堆栈帧大小。

现在堆栈帧通常包含以下内容：

指向父方法堆栈帧的帧指针
一个return地址
方法的参数
方法声明的局部变量
保存中间值所需的任何未命名临时变量。

实际计数将取决于方法的代码，以及 JIT 编译器如何将变量映射到堆栈帧中的槽。

显然，您的函数非常不同，它们需要不同大小的堆栈。我尚未对此进行验证，但我怀疑是 println 语句在执行此操作。或者更具体地说，需要额外的隐藏变量来保存连接字符串参数时使用的中间变量。

如果您想确定，您需要查看 JIT 编译器发出的代码。

为什么我在 Java 中的递归不会导致 StackOverflowError？

Why does my recursion in Java not result in a StackOverflowError?

java

stack-overflow

recursion