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

For the purposes of estimating the maximum call depth a recursive method may achieve with a given amount of memory, what is the (approximate) formula for calculating the memory used before a stack overflow error is likely to occur?

Edit:

Many have responded with "it depends", which is reasonable, so let's remove some of the variables by using a trivial but concrete example:

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

It is easy to show that running this in my Eclipse IDE explodes for n just under 1000 (surprisingly low to me). Could this call depth limit have been estimated without executing it?

Edit: I can't help thinking that Eclipse has a fixed max call depth of 1000, because I got to 998, but there's one for the main, and one for the initial call to the method, making 1000 in all. This is "too round" a number IMHO to be a coincidence. I'll investigate further. I have just Dux overhead the -Xss vm parameter; it's the maximum stack size, so Eclipse runner must have -Xss1000 set somewhere

Edit Report

1 Answer

Only a partial answer: from JVM Spec 7, 2.5.2, stack frames can be allocated on the heap, and the stack size may be dynamic. I couldn't say for certain, but it seems it should be possible to have your stack size bounded only by your heap size:

Because the Java virtual machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated.

and

This specification permits Java virtual machine stacks either to be of a fixed size or to dynamically expand and contract as required by the computation. If the Java virtual machine stacks are of a fixed size, the size of each Java virtual machine stack may be chosen independently when that stack is created.

A Java virtual machine implementation may provide the programmer or the user control over the initial size of Java virtual machine stacks, as well as, in the case of dynamically expanding or contracting Java virtual machine stacks, control over the maximum and minimum sizes.

So it'll be up to the JVM implementation.

answered 2012-12-21T19:20:37.043

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

Edit:

1 Answer

Your Answer