Exception in thread “main” java.lang.StackOverflowError

Your algorithm is fine. However int is too small for your computations, it fails for this input:

printSyra(113383, 1);

At some point integer overflows to negative value and your implementation goes crazy, recursing infinitely. Change int num to long num and you’ll be fine – for some time. Later you’ll need BigInteger.

Note that according to Wikipedia on Collatz conjecture (bold mine):

The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps. For starting numbers less than 1 billion it is 670,617,279, with 986 steps, and for numbers less than 10 billion it is 9,780,657,630, with 1132 steps.

The total number of steps is equivalent to maximum nesting level (stack depth) you can expect. So even for relatively big numbers StackOverflowError should not occur. Have a look at this implementation using BigInteger:

private static int printSyra(BigInteger num, int count) {
    if (num.equals(BigInteger.ONE)) {
        return count;
    if (num.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
        return printSyra(num.divide(BigInteger.valueOf(2)), count + 1);
    } else {
        return printSyra(num.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE), count + 1);

It works even for very big values:

printSyra(new BigInteger("9780657630"), 0)  //1132
printSyra(new BigInteger("104899295810901231"), 0)  //2254

Leave a Comment