如何预测递归方法的最大调用深度？

memory java recursion stack-overflow jvm

2022-08-31 22:11:00

为了估计递归方法在给定内存量下可能达到的最大调用深度，在可能发生堆栈溢出错误之前计算所用内存的（近似）公式是什么？

编辑：

许多人用“它取决于”来回应，这是合理的，所以让我们通过使用一个简单但具体的例子来删除一些变量：

public static int sumOneToN(int n) {
    return n < 2 ? 1 : n + sumOneToN(n - 1);
}

很容易证明在我的Eclipse IDE中运行它爆炸不到1000（对我来说低得惊人）。是否可以在不执行此调用深度限制的情况下估计它？n

编辑：我不禁认为Eclipse有一个固定的最大调用深度1000，因为我得到了，但是有一个用于主调用，一个用于对方法的初始调用，总共进行。恕我直言，这个数字“太圆”了，不是巧合。我将进一步调查。我只是Dux开销-Xss vm参数;这是最大堆栈大小，因此 Eclipse 运行器必须设置在某个位置9981000-Xss1000

答案 1

这显然是JVM-，也可能是特定于架构的。

我测量了以下内容：

  static int i = 0;
  public static void rec0() {
      i++;
      rec0();
  }

  public static void main(String[] args) {
      ...
      try {
          i = 0; rec0();
      } catch (StackOverflowError e) {
          System.out.println(i);
      }
      ...
  }

用

Java(TM) SE Runtime Environment (build 1.7.0_09-b05)
Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode)

在 x86 上运行。

对于 20MB 的 Java 堆栈（），摊销成本在每个调用大约 16-17 个字节之间波动。我见过的最低是16.15字节/帧。因此，我的结论是，成本为16字节，其余的是其他（固定）开销。-Xss20m

采用单个函数的开销基本相同，为 16 字节/帧。int

有趣的是，一个需要10个的函数需要32个字节/帧。我不知道为什么成本这么低。ints

上述结果在代码经过 JIT 编译后适用。在编译之前，每帧成本要高得多。我还没有找到一种方法来可靠地估计它。但是，这确实意味着在能够可靠地预测递归函数是否已 JIT 编译之前，您没有希望可靠地预测最大递归深度。

所有这些都是用128K和8MB的堆栈大小进行测试的。两种情况下的结果都是相同的。ulimit

答案 2

只有部分答案：从 JVM Spec 7，2.5.2 开始，堆栈帧可以在堆上分配，并且堆栈大小可能是动态的。我不能肯定地说，但似乎应该有可能让你的堆栈大小只受堆大小的限制：

由于除了推送和弹出帧之外，从不直接操作 Java 虚拟机堆栈，因此可以堆分配帧。

和

此规范允许 Java 虚拟机堆栈具有固定大小，或者根据计算的需要动态扩展和收缩。如果 Java 虚拟机堆栈的大小是固定的，那么在创建每个 Java 虚拟机堆栈时，可以独立选择该堆栈的大小。

Java 虚拟机实现可以为程序员或用户提供对 Java 虚拟机堆栈初始大小的控制，以及在动态扩展或收缩 Java 虚拟机堆栈的情况下，控制最大和最小大小。

因此，这将取决于JVM的实现。