Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Exception in thread "main" java.lang.StackOverflowError

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)
like image 569
Ray.R.Chua Avatar asked Oct 07 '12 15:10

Ray.R.Chua


People also ask

Can we handle StackOverflowError?

To handle StackoverFlowError, you should carefully inspect the stack trace to detect any repeating call patterns in your code. These indicate recursive calls to your code or function. Some traits of recursion: Large thread stacks that appear to repeat.

How do I fix Java Lang exception?

We can resolve the java. lang. ExceptionInInitializerError by ensuring that static initializer block of classes does not throw any Runtime Exception.

What is a StackOverflowError?

A stack overflow is a type of buffer overflow error that occurs when a computer program tries to use more memory space in the call stack than has been allocated to that stack.


2 Answers

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
like image 123
Tomasz Nurkiewicz Avatar answered Oct 14 '22 00:10

Tomasz Nurkiewicz


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.

like image 38
jonvuri Avatar answered Oct 14 '22 01:10

jonvuri