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

Question

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

许多人回答说“视情况而定”，这是合理的，所以让我们用一个琐碎但具体的例子来删除一些变量：

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

很容易看出，在我的EclipseIDE中运行它时，n的爆炸性增长不到1000（对我来说，这个数字低得出奇）。这个调用深度限制是否可以在不执行的情况下进行估计？

编辑：我忍不住认为Eclipse有一个固定的最大调用深度1000，因为我得到了998，但有一个用于main，还有一个用于方法的初始调用，使1000。这是一个“太圆”的数字，不可能是巧合。我会进一步调查的。我只是在-Xss vm参数上增加了Dux开销；这是最大堆栈大小，因此Eclipse runner必须在某个地方设置-Xss1000

Answer 1

补充NPEs答案：

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

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();
    }
}

输出为：

10825
10825
59538
59538
59538
59538
59538
59538
59538
59538

我使用了这个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)

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

Answer 2

只有部分答案：根据JVM规范7，2.5.2，可以在堆上分配堆栈帧，并且堆栈大小可能是动态的。我不能确定，但似乎应该可以让堆栈大小仅受堆大小的限制：

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

和

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

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

所以这取决于JVM实现。

Answer 3

这显然是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个整数的函数需要32字节/帧。我不知道为什么成本这么低。

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

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