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

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字节。

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

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

所有这些都通过ulimit128K和8MB 的堆栈大小进行了测试。在两种情况下结果都是相同的。