Can anybody explain to me why I am getting Stack Overflow Error?

Question

Im trying to complete the Project Euler question and attempting to do a recursive solution, but I am getting Stack overflow Error and cant seem to figure out why.

Any help would be great.

Thanks

public class Collatz {

public static void main(String[] args) {

    List<Integer> length = new ArrayList<Integer>();

    for(int i = 13; i < 1000000; i++){
        length.add(collat(i, 0));
    }
}

public static int collat(int x, int c){

    if(x == 1){
        return c;
    }

    if(x % 2 == 0){
        return collat(x/2, c + 1);
    }else{
        return collat((3 * x) + 1, c + 1);
    }
}
}

try the solution posted here http://stackoverflow.com/questions/860550/stack-overflows-from-deep-recursion-in-java — Robin Chander, Dec 20 '13 at 19:52
Have you tried using a debugger to see what `i` is when the error is occuring? — Danny, Dec 20 '13 at 19:52
you could change the command line options to change the stack size -Xss... see http://stackoverflow.com/questions/3700459/how-to-increase-to-java-stack-size — ghostbust555, Dec 20 '13 at 19:53
Instead of saying "Project euler question," please tell us what problem you are trying to solve. — Dennis, Dec 20 '13 at 19:54
I would use Dynamic Programming to reduce your recursive calls. — C.B., Dec 20 '13 at 19:55
@ChristopherHarris That doesn't help. Questions should be self-contained, not refer to outside sources — Dennis, Dec 20 '13 at 19:55
This is what's (slightly incorrectly) called "infinite recursion". — Hot Licks, Dec 20 '13 at 19:55
@HotLicks: The exception only indicates that a fixed stack size was exceeded. It does not indicate there is an infinite recursion. In fact, there is not. The Collatz sequence is known to be finite for all the samples in this Project Euler problem. — Eric Postpischil, Dec 20 '13 at 19:59
@EricPostpischil - Right. And as I implied, there's actually no such thing as "infinite" recursion. What happens is that the method recurs beyond the ability of the stack to contain the method instances. — Hot Licks, Dec 20 '13 at 20:02
so why not set -Xss to a large value ? -Xss8m should suffice ... — Amir Afghani, Dec 20 '13 at 20:03
@HotLicks: How is there no such thing as infinite recursion? What do you think `void foo(void) { foo(); }` does? — Eric Postpischil, Dec 20 '13 at 20:05
somethings not right in this program....i'm debugging it and i set -Xss to 100m and it still overflows... — Amir Afghani, Dec 20 '13 at 20:07
@EricPostpischil - It recurs until it blows the stack -- a fraction of a second. Hardly "infinite". — Hot Licks, Dec 20 '13 at 20:09
@HotLicks: That is merely the implementation. The program specified by the source code recurses infinitely. The fact that we cannot execute this program is irrelevant. We are limited, mathematics is not. In this case, the meaning of “infinite” is that, no matter how many resources we provide for the execution of the program, it will continue recursing. — Eric Postpischil, Dec 20 '13 at 20:16
@HotLicks I think we can come up with a mathematical definition to distinguish the two. If, for a program with any given inputs, there is a finite stack size, however large, that would enable the program to complete (assuming we were running on a machine with unlimited address space), it's not infinite. If there is no such stack size, it's infinite. That's why Eric's example is infinite recursion and the Euler problem isn't. — ajb, Dec 20 '13 at 20:26
@user3058210: I suggest you mark [Sean M.’s answer](http://stackoverflow.com/a/20711411/298225) as accepted instead of mine. — Eric Postpischil, Dec 20 '13 at 20:36

score 4 · Answer 1 · edited May 23 '17 at 12:28

4

Sean M. is correct; integer overflow is occurring. That answer should be marked as accepted.

edited May 23 '17 at 12:28

Community

1
1

answered Dec 20 '13 at 19:58

Eric Postpischil

195,579
13
168
312

1

Of course iteration is better for this kind of problem, but the stack overflow is still a mystery. According to http://en.wikipedia.org/wiki/Collatz_conjecture, "The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps". That shouldn't overflow the stack. – Guntram Blohm Dec 20 '13 at 20:01
If you want to increase the stack space experimentally you can set -Xss, but I agree with this response in principle. – Amir Afghani Dec 20 '13 at 20:01
Just for grins insert a depth counter and see how deep you go for a solution. – Hot Licks Dec 20 '13 at 20:12

Sean M. · Answer 2 · 2013-12-20T20:37:53.187

2

It looks like you are encountering an Integer Overflow. I just added this simple check for it in your collat() function.

if(x < 0) System.out.println("Overflow");

The overflow is occuring at step 121 in the sequence. Using a larger datatype should solve the issue.

edited Dec 20 '13 at 20:37

answered Dec 20 '13 at 20:25

Sean M.

118
5

score 0 · Answer 3 · answered Dec 20 '13 at 19:52

0

Because you are running out of the default stack size of 128k? Increasing stack size can fix this.

Read this: http://goo.gl/iy77Pr

answered Dec 20 '13 at 19:52

Amit Sharma

5,844
5
25
34

score 0 · Accepted Answer · edited May 23 '17 at 10:32

You need Longs, not Integers

Project Euler Question 14 (Collatz Problem)

My suggested solution, with DP

public class Collatz {


public static void main(String[] args) {

    List<Long> length = new ArrayList<Long>();

    Map<Long,Long> dict = new HashMap<Long,Long>();

    for(int i = 13; i < 1000000; i++){
            length.add(collat(i, 0,dict));

    }
}

public static long collat(long x, long c, Map<Long,Long> dict){


    if(dict.containsKey(x))
    {
        return dict.get(x);
    }

    if(x == 1){
        dict.put(x, c);
        return c;
    }

    else
    {
        if(x % 2 == 0){
            dict.put(x, collat(x/2, c + 1,dict));
            return dict.get(x);
            }else{
                dict.put(x,collat((3 * x) + 1, c + 1,dict));
                return dict.get(x);
            }
        }
    }

}

Can anybody explain to me why I am getting Stack Overflow Error?

4 Answers4