Exception in thread “main” java.lang.StackOverflow

Question

I have a piece of code and I could not figure out why it is giving me Exception in thread "main" java.lang.StackOverflowError.

This is the question:

Given a positive integer n, prints out the sum of the lengths of the Syracuse 
sequence starting in the range of 1 to n inclusive. So, for example, the call:
lengths(3)
will return the the combined length of the sequences:
1
2 1
3 10 5 16 8 4 2 1 
which is the value: 11. lengths must throw an IllegalArgumentException if 
its input value is less than one.

My Code:

import java.util.HashMap;

public class Test {

HashMap<Integer,Integer> syraSumHashTable = new HashMap<Integer,Integer>();

public Test(){

}

public int lengths(int n)throws IllegalArgumentException{

    int sum =0;

    if(n < 1){
        throw new IllegalArgumentException("Error!! Invalid Input!");
    }   

    else{


        for(int i =1; i<=n;i++){

            if(syraSumHashTable.get(i)==null)
            {
                syraSumHashTable.put(i, printSyra(i,1));
                sum += (Integer)syraSumHashTable.get(i);

            }

            else{

                sum += (Integer)syraSumHashTable.get(i);
            }



        }

        return sum;

    }



}

private int printSyra(int num, int count){

    int n = num;

    if(n == 1){

        return count;
    }

    else{   
            if(n%2==0){

                return printSyra(n/2, ++count);
            }

            else{

                return printSyra((n*3)+1, ++count) ;

            }

    }


}
}

Driver code:

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Test s1 = new Test();
    System.out.println(s1.lengths(90090249));
    //System.out.println(s1.lengths(5));
}

. I know the problem lies with the recursion. The error does not occur if the input is a small value, example: 5. But when the number is huge, like 90090249, I got the Exception in thread "main" java.lang.StackOverflowError. Thanks all for your help. :)

I almost forgot the error msg:

Exception in thread "main" java.lang.StackOverflowError
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:65)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:65)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)

Answer 1

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

Answer 2

One solution is to allow the JVM to take more space for stack recursion, using the java -Xss parameter. Its default is less than a megabyte, IIRC, which could limit to a couple of hundred recursions max.

A better solution is to rewrite the exercise without recursion:

private int printSyra(int num){
    int count = 1;    
    int n = num;    
    while(n != 1){

            if(n%2==0){    
                n = n/2;
                ++count;
            }    
            else{    
                n=(n*3)+1;
                ++count;    
            }    
    }
    return count;
}

Answer 3

This is an inherent problem with recursive algorithms. Make the number of recursions large enough and you can't really avoid a stack overflow, unless the language can guarantee tail-call optimization (Java and most C-like languages don't). The only way to truly fix it is to "unroll" the recursion, rewriting the algorithm iteratively or with a helper function to simulate the state-passing of the recursive call without actually nesting calls.