Robert Robert - 2 months ago 11
Java Question

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

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 !!

Answer

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;

}
Comments