How many function calls will cause stack overflow

Question

Hello android/Java developers,

When a function call a function and that function call another one and so on, how many calls (stack length) would get me into stack over flow? Is there a general rule of thumb?

The reason i am asking is because I am now which is more efficient(design wise) for my 5 players cards game

Solution 1:

for(int i=0;i<100;i++){
         p1.play();
         p2.play();
         p3.play();
         p4.play();
}

Solution 2:

   p1.play();    //where p1.play() calls p2.play() and so on until p4 calls p1 again.   
                 // this will go on for 100 times

I prefer solution 2 so if there is a crash I can see all the function calls from p1 at i=0 till p4 at i=100

but with solution 1, the stack is much shorter but when there is a crash I will see on the beginning of the loops a the called function play() where crash happened

What do you suggest? I know it is kinda 2 questions in 1 but they are very related

Thank you all

Answer 1

In my experience, a stack overflow in Java is almost always due to a programming error. See typical sizes here.

Now, your second solution is, IMO, quite ugly... almost a programming error. Assuming N=100 is (sort of) the duration of your game, it sounds just wrong that the memory consumption (stack size) increases with it. I don't like that solution at all.

when there is a crash I will see on the beginning of the loops a the called function play() where crash happened

I don't see the real advantage. Why not put a try catch block so that in case of a crash you can print out the iteration number?

Answer 2

There is no general rule of thumb for recursive or nested functions creating a stack overflow. Instead it is dependent on the memory available on the stack, which may vary depending on underlying hardware and operating system allocations.

It is difficult to determine which method of function calls is better for your situation without seeing more of the code. I would side with the former (first) option because it is a little more explicit towards what is happening, and it avoids linking together possible methods and object instances that may not necessarily be dependent on one another. If you are primarily concerned by error reports, you can try adding Logs into your code to allow for more verbose knowledge of what is going on, along with looking at the dump of the stack trace. Hopefully this link can help you as well: http://developer.android.com/tools/debugging/index.html

Answer 3

I think Shivan Dragon is right, there is no fix amount of calls, that will cause an overflow. However you can test it with a really simple recursive function:

public void stackTest(int iteration)
{
    System.out.println("Iteration: "+iteration); // or Log
    stackTest(iteration+1);
}

And call it like:

stackTest(1);

and then see how far it goes.

Answer 4

I don't think you can say that a general number of x function calls will trigger an overflow of the stack memory. It depends on the functions, their arguments, their return types etc, all are kept on the stack memory, so different functions may take different amounts of (stack) memory.

At any rate, you should never rely on code that gets even remotely close to crashing the stack by trying to take into account how much of the stack is used. Your code should always be waaay clear of overflowing the stack.

Answer 5

Each method's frame in Java has: local variables table and operands stack. This stack size is constant and each method might have different size of it. Due to JVM specification the operand stack size is stored in methods attribute Code in max_stack field:

Code_attribute {
    u2 attribute_name_index;
    u4 attribute_length;
    u2 max_stack;
    u2 max_locals;
    u4 code_length;
    u1 code[code_length];
    u2 exception_table_length;
    {   u2 start_pc;
        u2 end_pc;
        u2 handler_pc;
        u2 catch_type;
    } exception_table[exception_table_length];
    u2 attributes_count;
    attribute_info attributes[attributes_count];
}

This size is calculated during compilation and might be changed by JVM when you hit StackOverflowException. JVM specification:

The following exceptional conditions are associated with Java virtual machine stacks: If the computation in a thread requires a larger Java virtual machine stack than is permitted, the Java virtual machine throws a StackOverflowError. If Java virtual machine stacks can be dynamically expanded, and expansion is attempted but insufficient memory can be made available to effect the expansion, or if insufficient memory can be made available to create the initial Java virtual machine stack for a new thread, the Java virtual machine throws an OutOfMemoryError.

To sum up: it depends how much memory your JVM is permitted to obtain. On different workstations/smartphones you might have different values of available memory. This is why you shouldn't write code which is dependent on such things. If you think that OutOfMemoryException might occur try to solve your problem iterative instead of recursive.

Answer 6

This come down to the principle of recursion vs iteration.

Recursion allows you to write an algorithm in a simple manner; easier to understand and quicker to implement. Recursive algorithms can be converted to iterative algorithms which will be more memory efficient and more cpu efficient.

So the decision is one of performance vs simplicity/coding effort.

Here is a thread about this topic: Recursion or Iteration?