How can i avoid the java.lang.StackOverflowError:null?

Question

I'm trying to learn Java a bit on my own and normally I have more then enough resources with good site's like these, but now I just want to know where I'm wrong.

So the problem was phrased as :

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

I keep getting these java.lang.StackOverflowError, could someone help me please. My code:

import java.util.HashMap;

public class Euler
{
    HashMap<Integer,Integer> check;
    int result;

    public Euler()
    {
        check = new HashMap<Integer,Integer>();     
    }

    public int search(int number)
    {

        int startingNumber = number;

        while (check.get(number)==null && number!=1){

            if (number%2==0){
                number = number / 2;
                result = search(number);
                result++;               
            }

            else {
                number = (3*number)+1;
                result = search(number);
                result++;
            }
        }

        if (check.get(startingNumber)!=null){
            result=result+check.get(number);
            check.put(startingNumber,result);

        }
        else{
            check.put(startingNumber,result);
        }

        return result;
    }

    public int test()
    {
        int temp = 0;
        int highest=0;
        int get = 0;
        for (int i=1000001;i>1;i--){
            result = 0;
            temp = search(i);
            if(temp>highest){
                highest=temp;
                get = i;
            }
            System.out.println(i);
        }

        return get;
    }


}

EDIT:

public class Euler
{
   public Euler()
    {
    }

    public int quickSearch(int numb)
    {
        int steps = 0;
        while (numb != 1) {
            if (numb % 2 == 0) {
                numb /= 2;
            }
            else {
                numb = 3 * numb + 1;
            }
            steps++;
        }
        return steps;
    }


    public int test()
    {
        int temp = 0;
        int highest=0;
        int get = 0;
        for (int i=1;i<1000001;i=i+2){

            temp = quickSearch(i);
            if(temp>highest){
                highest=temp;
                get = i;
            }
            System.out.println(i);

        }

        return get;
    }
}

EDIT2: So in the EDIT version code, i got a freeze from the machine, but when i changed int to long, it worked perfectly, although I understand that with some Map to store values, you can find it faster. Thank you all !!

"i'm trying to learn javascript" - Java and JavaScript are not the same language. Your code is Java — JonK, Sep 28 '16 at 10:48
Why do you use a hashmap to store the result and the starting number for that result? Looking stuff up from a hashmap is prpbably slower than multiplying it by 3 and adding 1 or dividing it by 2 — Bálint, Sep 28 '16 at 10:50
@Bálint I store it in a hashmap, so when i already encounter a number that's already been processed, i take the value and add plus 1, and store it too. Or is that silly ? — Robert, Sep 28 '16 at 10:57
Use a debugger to find out. Hint: you are recurring without a terminating condition. Your map never gets updated because you infinitely recurse before updating the map. — Erwin Bolwidt, Sep 28 '16 at 11:02
@Robert again, looking up things from a hashmap is probably slower than the actual algorithm — Bálint, Sep 28 '16 at 11:12

Leon · Accepted Answer · 2016-09-28T11:41:07.833

The problem is, that you have too many recursive calls. The best resolution for this would be to make the code iterative. Just rework your while loop to first check whether the number was found already if yes return the sum of the steps it took you to get to that number and it will take to get from that number to 1. Otherwise just update the number for the next step, run through the loop again. Meanwhile, you just have to keep track of the steps it took you to get to a known number.

Personally, I would remove the HashMap altogether and just have a simple while loop:

int steps = 0;
while (number != 1) {
    if (number % 2 == 0) number /= 2;
    else number = 3 * number + 1
    steps++;
}

Edit: If you want to add a HashMap to store found values, you could do it like this (I assume you defined a HashMap<Long, Integer> named foundNumbers earlier):

public int search(long number) {

    int steps = 0;
    long initialNumber = number;
    while (number != 1) {
        if (number % 2 == 0) number /= 2;
        else number = 3 * number + 1
        steps++;

        if (foundNumbers.containsKey(number)) {
            steps += foundNumbers.get(number)
            foundNumbers.put(initialNumber, steps);
            return steps;
        }
    }

    foundNumbers.put(initialNumber, steps);
    return steps;

}

so you mean like the code at EDIT ? but then it stops at 113381 and won't move ... — Robert, Sep 28 '16 at 11:30
I found [this question](http://stackoverflow.com/questions/32531130/how-to-avoid-stackoverflow-at-collatz-for-high-values) and it seems to be the same exercise. Looking in the comments, it seems like `int` is too small for your numbers. Maybe try a `long`. Additionally, if it takes too long, you can try to add a `HashMap` to save found values (like you already did in your original code, just with iteration instead of recursion) to cut the time needed. — Leon, Sep 28 '16 at 11:35

score 0 · Answer 2 · answered Sep 28 '16 at 11:44

0

Although recursion code is easy and compact in many cases but there is possibility of stack overflow, especially if the length of recursion chain is unknown.

Your case is simple and can be easily tackled by iteration. So, try using iterative model instead of recursive model.

answered Sep 28 '16 at 11:44

Amber Beriwal

1,568
16
30

if you use iteration, are you not doing some calculations double ? If you take the number 3, it's : 3 10 5 16 8 4 2 1, and when you're later taking the number 10, he makes the whole calculation, while if I use recursion, the numbers 10,5,16,8,4,2 are saved immediately, so when you come to 10 he doesn't have to calculate anymore ? – Robert Sep 28 '16 at 11:55
You can control that in loop as well using a `HashMap`, in the same way as you maintain it in recursion. – Amber Beriwal Sep 28 '16 at 12:36

score -1 · Answer 3 · answered Sep 28 '16 at 10:56

-1

The problem is here:

public int search(int number)
{

    int startingNumber = number;

    while (check.get(number)==null && number!=1){

        if (number%2==0){
            number = number / 2;
            result = search(number);
            result++;               
        }

        else {
            number = (3*number)+1;
            result = search(number);
            result++;
        }
    }

    if (check.get(startingNumber)!=null){
        result=result+check.get(number);
        check.put(startingNumber,result);

    }
    else{
        check.put(startingNumber,result);
    }

    return result;
}

You call search(int) recursively and it cause stacking.

answered Sep 28 '16 at 10:56

Shaq

377
5
16

if (number%2==0){ number = number / 2; result = search(number); result++; } else { number = (3*number)+1; result = search(number); result++; } – Shaq Sep 28 '16 at 10:57
The problem is possibly here ;) http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror – Shaq Sep 28 '16 at 10:58

How can i avoid the java.lang.StackOverflowError:null?

3 Answers3