如何预测一个递归方法的最大调用深度？(How to predict the maximum call

用于估计最大呼叫深度递归方法可以与给定内存量达到的目的，是什么（近似）计算公式使用前一堆栈溢出错误可能发生的存储器？

编辑：

很多人回答说：“这取决于”，这是合理的，所以我们用微不足道，但具体的例子删除一些变量：

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编译。

所有这一切都与一个测试ulimit的128K和8MB堆栈大小。结果是在这两种情况下是相同的。

Answer 2:

仅是部分的答案：从JVM规格7，2.5.2 ，堆栈帧可以在堆上分配，并且堆栈大小可以是动态的。我不能肯定地说，但现在看来，这应该可以有你的堆栈大小仅受堆大小为界：

因为Java虚拟机堆从不直接操纵除了压入和弹出的帧，帧可以是堆分配。

和

本说明书中允许Java虚拟机的堆要么是固定大小的或所要求的计算来动态地扩展和收缩。如果Java虚拟机堆的大小是固定的，每一个Java虚拟机的堆的大小可以独立地被创建堆栈时选择的。
Java虚拟机实现可以提供程序员或过Java虚拟机堆的初始大小的用户控制，以及，在动态扩展或以上的最大和最小尺寸收缩Java虚拟机栈，控制的情况下。

因此，这将是最多的JVM实现。

Answer 3:

Addig到NPE的答案：

最大堆栈深度似乎是灵活的 。下面的测试程序打印截然不同的数字：

public class StackDepthTest {
    static int i = 0;

    public static void main(String[] args) throws Throwable {
        for(int i=0; i<10; ++i){
            testInstance();
        }
    }

    public static void testInstance() {
        StackDepthTest sdt = new StackDepthTest();
        try {
            i=0;
            sdt.instanceCall();
        } catch(StackOverflowError e){}
        System.out.println(i);
    }

    public void instanceCall(){
        ++i;
        instanceCall();
    }
}

输出是：

我用这个JRE的默认：

java version "1.7.0_09"
OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu1~12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

所以得出的结论是：如果脓有足够的（即两次以上），你得到第二次机会;-)