Random StackOverflowError in recursive calculation

Question

When executing the code inserted below in Eclipse about 1 out of 3 times, the following exception occurs:

Exception in thread "main" java.lang.StackOverflowError at src.Adder.recursiveSumAllNumbersUpTo(Driver.java:33) at src.Adder.recursiveSumAllNumbersUpTo(Driver.java:37) ... *(there are 1024 lines in this stack)* 

Another 2 times, it spills out the result as intended (the time between them changes slightly):

 Recursive: 467946 Non Recursive: 61282 Difference between recursive and non-recursive: 406664 Sum from recursive add: 19534375 Sum from non-recursive add: 19534375 

Why does the exception occur (apparently) ~ 30% of the time?

Here is the code:

 public class Driver { public static void main(String[] args) { Adder adder = new Adder(); int valueToSumTo = 6250; long startTime = System.nanoTime(); int raSum = adder.recursiveAddAllNumbersUpTo(valueToSumTo); long endTime = System.nanoTime(); long raDif = endTime - startTime; System.out.println("Recursive: " + (raDif)); startTime = System.nanoTime(); int nonRaSum = adder.nonRecursiveAddAllNumbersUpTo(valueToSumTo); endTime = System.nanoTime(); long nonRaDif = endTime - startTime; System.out.println("Non Recursive: " + (nonRaDif)); System.out.println("Difference between recursive and non-recursive: " + (raDif - nonRaDif)); System.out.println("Sum from recursive add: " + raSum); System.out.println("Sum from non-recursive add: " + nonRaSum); } } class Adder { public int recursiveAddAllNumbersUpTo(int i) { if (i == 1) { return i; } return i + recursiveAddAllNumbersUpTo(i - 1); } public int nonRecursiveAddAllNumbersUpTo(int i) { int count = 0; for(int num = 1; num <= i; num++) { count += num; } return count; } } 

Answer 1

Every time a recursive method calls itself, everything goes onto the stack, and an algorithm like yours requires a very deep stack.

To solve your problem, you must increase the size of the stack.

You can do this by invoking the JVM with the -Xss option.

If you use Eclipse, you can do this by following these steps:

• Right-click your project → Run as → Run configurations;
• Go to the "Arguments" tab; On the VM arguments write: "-Xss4m"

Try to increase the stack if this configuration is not enough.

Answer 2

try to see if it might be useful:

FROM ( http://www.odi.ch/weblog/posting.php?posting=411 )

Java stack size myths

How Java uses the stack mostly without documents. Therefore, we, the developers, stay with us. Today I wrote some interesting test codes that Results. For my tests, I used Sun JDK 1.5.0_12 under RedHat Enterprise Linux 3.

At first, I wanted to know the stack size that the VM chooses for threads. I found that the ulimit -s option does not directly affect the stack size selected by the virtual machine. The default is apparently 512kb, and can freely change with the -Xss and -XX: ThreadStackSize options. But I could not find a difference in behavior between these parameters. They seem to be doing the same. I further discovered that this Linux machine can create new threads at about 5000 per second.

I performed these tests by creating new threads and setting them to sleep in a blocking wait call immediately. I continued to create threads until the VM ran out of memory. With 512k stacks, the number of threads was about 3700, for 256k stacks about 7300, for 128k about 13700.

This leads to the following memory consumption by the stacks: 3700 x 512 kB = 1850 MB 7300 x 256 kB = 1825 MB 13700 x 128kB = 1713MB

Of course, a 32-bit process is limited to 4 GB of address space (minus 1 or 2 GB for the kernel). Therefore, it is only natural that memory is close to these 2GB minus heap size. (Note that Stack is never allocated from the heap.)

Next, I checked how deeply I can access the recursive method until I get a stack overflow. I did this by changing the original program, so that each thread will be returned to the method until it hits the overflow stack, then they fall asleep. The thread recorded maximum recursion depth. That I got really strange results. Especially with a VM server, the maximum depth varies over a wide range between 1750 and 5700 calls (128 thousand Stacks)! It is far from constant that was my first guess. With a client VM, the number is usually lower but does not vary so much: between 1100 and 1650.

Also, the maximum depth is apparently lower at the beginning of the test and increases towards the end.

Answer 3

play with stack size: -Xss32m allows 32 Mo for the stack.
Note: AFAIK, java does not handle (why ?!) tail recursion optimization.