Intermittent stack overflow for recursion method

Question

I have a simple method that I wrote to specify the homework of a class that uses recursion (yes, it should use recursion) to calculate the number of triangles in a fractal pattern:

public static BigInteger triangleFract(int layer) { if(layer < 0) { throw new IllegalArgumentException("Input must be >= 0"); } else if(layer == 0) { return new BigInteger("0"); } else if (layer == 1) { return new BigInteger("1"); } else { return triangleFract(layer - 1) .multiply(new BigInteger("3")) .add(new BigInteger("2")); } } 

What I'm trying to do is understand how big the int level can be to limit user input. After some tests, I get a stack overflow of about 6700+, which is great.

What bothers me is that if the layer is in the thousands, the method usually executes, but it can still accidentally encounter a StackOverflowError .

For example, I decided to limit the level to 4444 and seems to be able to handle this almost always, but every time it overflows anyway.

Why is he doing this? And is there anything I can do about it?

Answer 1

Consider the transition to the iterative version. This is what I think, if you are developing a recursion algorithm, you should control the depth of the level or not use recursion at all.

Answer 2

Perhaps the JVM determined (through mileage analysis) that BigInteger could be allocated on the stack rather than on the heap. Depending on when it implements this optimization, the size of the required stack will vary.

However, there can be many other reasons, and the behavior is likely to depend on the JVM you are using.

Answer 3

Allow recursion to this depth is the smell of design.

Try this iterative version:

 public static BigInteger triangleFract(int layer) { if (layer < 0) { throw new IllegalArgumentException("Input must be >= 0"); } if (layer == 0) { return BigInteger.ZERO; } BigInteger result = BigInteger.ONE; BigInteger two = new BigInteger("2"); BigInteger three = new BigInteger("3"); for (int i = 1; i < layer; i++) { result = result.multiply(three).add(two); } return result; } 

Notes:

• Using BigInteger.ZERO and BigInteger.ONE instead of creating new instances for these values
• Removed redundant else - after the final statement there is no else (for example, return )
• Reusing new BigInteger("2") and new BigInteger("3") instead of creating new instances at each iteration

Answer 4

In fact, you can do: increase the maximum stack size. This is done when starting the JVM with the -Xss option as follows:

 java -Xss40m MainClass 

Be careful not to set the value too high. If you need to go more than 60 m - 70 m, it is recommended to redesign your code.

Answer 5

I could not reproduce the “fluctuation” effect. This is a pretty deterministic code, so you should get the same result every time (including an error).

How did you test it? Have you launched a new jvm for every attempt of your 4444 test? (or was it just the Frac triangle (4444) called in the loop?).

What is your OS, java version, etc.

I ask because I really don't like unresolved issues like this: something like this can bite you where (and when) it hurts;).

oh ... BTW, for all this, you should use the ONE and ZERO constants from BigInteger (and create your own for 2 and 3. In this case, you should save some memory (yes, I know, that was not your question).

Answer 6

For those who cannot reproduce this fluctuation. Find the layer value from which the method will throw StackOverflowError reliably. The closer this value is to the real threshold, the better. Now call this method from the loop (on my machine maxLayer = 11500 ):

 int i = 11500; while (true) { System.out.println(i); triangleFract(i++); } 

It will throw a StackOverflowError . Now slightly decrease this value (it seems like 5-10% should be enough):

 int i = 10500; while (true) { System.out.println(i); triangleFract(i++); } 

Well, on my machine this does not cause any error and successfully jumps over 11500 . In fact, it works fine up to 16000 .

So, whatever that is, it is probably related to JVM optimization. I tried to run the program using -XX:+PrintCompilation . I saw how JIT does its work during the loop:

 117 1 java.lang.String::hashCode (64 bytes) 183 2 java.lang.String::charAt (33 bytes) 189 3 sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes) 201 4 java.math.BigInteger::mulAdd (81 bytes) 205 5 java.math.BigInteger::multiplyToLen (219 bytes) 211 6 java.math.BigInteger::addOne (77 bytes) 215 7 java.math.BigInteger::squareToLen (172 bytes) 219 8 java.math.BigInteger::primitiveLeftShift (79 bytes) 224 9 java.math.BigInteger::montReduce (99 bytes) 244 10 sun.security.provider.SHA::implCompress (491 bytes) 280 11 sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (490 bytes) 282 12 java.lang.String::equals (88 bytes) 11400 289 13 java.lang.String::indexOf (151 bytes) 293 14 java.io.UnixFileSystem::normalize (75 bytes) 298 15 java.lang.Object::<init> (1 bytes) 298 16 java.util.jar.Manifest$FastInputStream::readLine (167 bytes) 299 17 java.lang.CharacterDataLatin1::getProperties (11 bytes) 300 18 NormalState::triangleFract (74 bytes) 308 19 java.math.BigInteger::add (178 bytes) 336 20 java.lang.String::lastIndexOf (151 bytes) 337 21 java.lang.Number::<init> (5 bytes) 338 22 java.lang.Character::digit (6 bytes) 340 23 java.lang.Character::digit (168 bytes) 342 24 java.lang.CharacterDataLatin1::digit (85 bytes) 343 25 java.math.BigInteger::trustedStripLeadingZeroInts (37 bytes) 357 26 java.lang.String::substring (83 bytes) 360 27 java.lang.String::lastIndexOf (10 bytes) 360 28 java.lang.String::lastIndexOf (29 bytes) 361 29 java.math.BigInteger::<init> (24 bytes) 361 30 java.lang.Integer::parseInt (269 bytes) 361 31 java.math.BigInteger::<init> (8 bytes) 362 32 java.math.BigInteger::<init> (347 bytes) 404 33 java.math.BigInteger::multiply (72 bytes) 404 34 java.math.BigInteger::add (123 bytes) 

Maybe this is a compilation? Try deferring the compilation so that it affects us as late as possible. I tried to play with the -XX:CompileThreshold and pretty soon found a value ( -XX:CompileThreshold=1000000 ) that prevents my loop from jumping over 11500 .

UPDATE

I finally played it without any compilation threshold setting. For me, it looks as if I were running the program in my IDE (IntelliJ IDEA). So this may be due to the IDEA launcher. I copied its command line and used it in a small script:

 for I in `seq 1 100`; do java ... com.intellij.rt.execution.application.AppMain \ Triangle 2>&1| grep Stack; done | wc -l 

And what I found out is he usually prints something less than 100 (95-98). This is consistent with what I saw when I did this manually. When I skip the launcher:

 for I in `seq 1 100`; do java \ Triangle 2>&1| grep Stack; done | wc -l 

he always prints 100.