How to predict the maximum call depth of a recursive method?

Question

In order to estimate the maximum call depth that a recursive method can achieve with a given amount of memory, what is the (approximate) formula for calculating the memory used before the error is likely to happen?

Edit:

Many answered "it depends", which is reasonable, so let me remove some variables using a trivial but concrete example:

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

It's easy to show that starting this in my Eclipse IDE explodes for n just under 1000 (surprisingly low for me). Is it possible that this call depth limit was estimated without its execution?

Edit: I can't help but think that Eclipse has a fixed maximum call depth of 1000, because I got to 998 , but there is one for the main one and one for the initial method call, making 1000 in all. This is "too cool" IMHO number to be a coincidence. I will explore further. I have only Dux overhead -Xss vm parameter; this is the maximum stack size, so the Eclipse runner should have -Xss1000 set somewhere

Answer 1

This is explicitly JVM - and perhaps also architecture specific.

I measured the following:

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

using

 Java(TM) SE Runtime Environment (build 1.7.0_09-b05) Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode) 

works on x86.

With a 20 MB Java stack ( -Xss20m ), the amortized cost ranged around 16-17 bytes per call. The lowest figure I saw was 16.15 bytes / frame. Therefore, I conclude that the cost is 16 bytes, and the rest is other (fixed) overhead.

A function that takes a single int has basically the same cost, 16 bytes / frame.

Interestingly, a function that accepts ten ints requires 32 bytes / frame. I'm not sure why the cost is so low.

The above results apply after compiling the JIT code. Before compilation, the cost of each frame is much higher. I still do not understand the way to reliably evaluate it. However, this means that you have no hope of reliably predicting the maximum depth of the recursion until you can reliably predict whether the recursive function was compiled by JIT.

All of this has been tested with the ulimit stack sizes of 128 KB and 8 MB. The results were the same in both cases.

Answer 2

Only a partial answer: from JVM Spec 7, 2.5.2 , frame stacks can be allocated on the heap, and the stack size can be dynamic. I could not say for sure, but it seems that the stack size can be limited only by your heap size:

Since the Java virtual machine stack is never controlled directly, except for push and pop frames, frames can be heaped.

and

This specification allows the Java virtual machine stacks to either be fixed size or dynamically expand and write off as per the calculation requirements. If the stacks of the Java virtual machine are of a fixed size, you can choose the size of each stack of the Java virtual machine, regardless of when this stack is created.

The implementation of the Java virtual machine can provide the programmer or the user with control over the initial size of the Java virtual machine stacks, as well as in the case of dynamic expansion or reduction of Java virtual machine stacks, control the maximum and minimum sizes.

So this will be the implementation of the JVM.

Answer 3

Answer: it all depends.

First of all, the size of Java Stack can be changed.

Secondly, the stack frame size of this method may vary depending on different variables. More information can be found in the section “Call Stack Frame Size” “Call Stack” - Wikipedia .

Answer 4

Addig answer to NPE:

The maximum stack depth seems flexible. The following test program prints significantly different numbers:

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

Output:

 10825 10825 59538 59538 59538 59538 59538 59538 59538 59538 

I used the default value for this 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) 

So, the conclusion: if you had enough pus (i.e. more than two times), you have a second chance; -)

Answer 5

depends on your system architecture (32 or 64-bit addresses), the number of local variables and method parameters. If tailing is not recursively overhead, if the compiler optimizes it in a loop.

You see, there is no simple answer.

Answer 6

You can take the empirical road and experiment with your code and the -Xss setting. See here for more details: JVM -Xss parameter - What does it do exactly?