如何预测recursion方法的最大通话深度?

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

编辑:

许多人回答“依赖”,这是合理的,所以让我们用一个简单而具体的例子来删除一些variables:

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

很容易certificate,在我的Eclipse IDE中运行这个在n下刚刚爆炸了1000(对我来说令人惊讶的低)。 这个通话深度限制是否已经被估计而不执行?

编辑:我不禁想到,Eclipse有一个固定的最大通话深度1000,因为我得到了998 ,但有一个主要的,一个最初的调用方法,总共1000 。 这是一个恕我直言,“太圆”是一个巧合。 我会进一步调查。 我只有Dux开销-Xss vm参数; 这是最大的堆栈大小,所以Eclipse runner必须在-Xss1000设置的地方

这显然是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编译之后。 在编译之前,每帧成本高得多。 我还没有想出一个可靠的估计方法。 然而,这确实意味着你不能可靠地预测最大recursion深度,直到你可以可靠地预测recursion函数是否被JIT编译。

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

只有部分答案: JVM Spec 7,2.5.2堆栈帧可以分配在堆上,并且堆栈大小可以是dynamic的。 我不能肯定地说,但似乎应该有可能让你的堆栈大小只有你的堆大小:

因为除了推送和popup帧之外,Java虚拟机堆栈不会被直接操作,因此可能会分配堆栈。

这个规范允许Java虚拟机栈或者是固定的大小,或者是按照计算的需要dynamic扩展和收缩。 如果Java虚拟机堆栈的大小是固定的,则每个Java虚拟机堆栈的大小可以在创build堆栈时独立select。

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

所以这将取决于JVM的实现。

答案是,这一切都取决于。

首先,Java堆栈大小可以改变。

其次,给定方法的堆栈帧大小可以根据不同的variables而变化。 您可以查看Call stack – 维基百科的Call Stack Frame Size部分以获取更多详细信息。

Addig到NPE回答:

最大堆栈深度似乎是灵活的 。 下面的testing程序打印了大量不同的数字:

 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) 

所以结论是:如果你的脓液已经够了(即超过两次),你有第二次机会;-)

取决于你的系统架构(32或64位地址),方法的局部variables和参数的数量。 如果是尾recursion没有开销,如果编译器优化它到一个循环。

你看,没有简单的答案。

你可以走实验路线,试验你的代码和-Xss设置。 请参阅此处了解更多信息: JVM选项-Xss – 具体做什么?