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

Question

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

编辑:

很多人的回答是“它取决于”，这是合理的，所以让我们通过一个琐碎但具体的例子来删除一些变量:

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

很容易证明，在我的 Eclipse IDE 中运行此代码会导致 n 的值低于 1000(对我来说太低了)。是否可以在不执行的情况下估计此调用深度限制？

编辑:我不禁想到 Eclipse 有一个固定的最大调用深度 1000，因为我得到了 998，但是有一个用于主，一个用于初始调用方法，总共制作1000。这是一个“太圆”的数字恕我直言，不是巧合。我会进一步调查。我刚刚 Dux 开销了 -Xss vm 参数；这是最大堆栈大小，因此 Eclipse 运行程序必须在某处设置 -Xss1000

Answer 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 堆栈 (-Xss20m)，每次调用的摊销成本在 16-17 字节左右波动。我见过的最低的是 16.15 字节/帧。因此，我得出结论，成本为 16 个字节，其余为其他(固定)开销。

采用单个 int 的函数具有基本相同的成本，16 字节/帧。

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

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

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