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);
}
}
}
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);
}
}
}
}