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

Question

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

编辑:

许多人回答"它依赖",这是合理的,所以让我们通过使用一个微不足道但具体的例子来删除一些变量:

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

很容易证明,在我的Eclipse IDE中运行它会爆炸n不到1000(对我来说非常低).这个调用深度限制是否可以在不执行的情况下估算？

编辑:我不禁认为Eclipse有一个固定的最大调用深度1000,因为我得到了998,但是有一个用于main,一个用于初始调用方法,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编译.

所有这些都经过测试,ulimit堆栈大小为128K和8MB.两种情况下的结果相同.

Answer 2

只有部分答案:来自JVM Spec 7,2.5.2,堆栈帧可以在堆上分配,堆栈大小可以是动态的.我无法肯定地说,但似乎应该可以让你的堆栈大小仅限于你的堆大小:

由于除了推送和弹出框架之外从不直接操作Java虚拟机堆栈,因此可以对堆进行堆分配.

和

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

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

所以它取决于JVM的实现.