Intermittent Stack Overflow for Recursion Method

Question

I have a simple method I've written for a class homework assignment that uses recursion (yes, it must 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've been trying to do is understand how big the int layer can be so as to limit user input. After some tests I get a stack overflow at around 6700+, which is fine.

What is troubling me is that if layer is in the thousands, the method usually runs, but it can still randomly encounter a StackOverflowError.

For instance, I chose to limit layer to 4444, and it seems to be able to handle that almost always, but every once in a while it still seems to overflow.

Why does it do this? And is there anything that I can do about it?

Answer 1

Perhaps the JVM has determined (through escape analysis) that the BigInteger can be allocated on the stack rather than the heap. Depending on when it implements this optimization, the required stack size would vary.

That said, there could be many other causes, and the behaviour is likely to depend on the JVM you use.