I've lurked around for years, but today I have a question concerning my code. I am currently trying to create a collatz program that puts the number of steps for a certain number in an array, but at the same time puts the number of steps for every single number it passes through. Here's my code:
public class GenerousRecursion {
public static short steps;
public static int length;
public static short[] array = new short[101];
public static void main(String[] args) {
length = 100;
for (int count = 2; count < length + 1; count++){
steps = 0;
System.out.println(count + ": " + findCollatz(count));
}
}
public static short findCollatz(int number) {
if (number < length){
if (array[number] > 0) {
steps = array[number]++; return steps;
}
else if(number % 2 == 0) {
array[number] = findCollatz(number / 2);
steps ++;
return steps;
}
else {
array[number] = findCollatz(3 * number + 1);
steps ++;
return steps;
}
}
else {
if(number % 2 == 0) {
findCollatz(number / 2);
steps ++;
return steps;
}
else {
findCollatz(3 * number + 1);
steps ++;
return steps;
}
}
}
}
Here's a great video on the Collatz Conjecture: Numberphile
So here is the error being thrown (reduced), but I don't understand, because I am not anywhere near the bounds of any int or short:
Exception in thread "main" java.lang.StackOverflowError
at GenerousRecursion.findCollatz(GenerousRecursion.java:22)
at GenerousRecursion.findCollatz(GenerousRecursion.java:33)
at GenerousRecursion.findCollatz(GenerousRecursion.java:27)
I just listed these first three lines because these same three lines draw errors for hundreds of lines.
Whats the problem and how do I fix it? Thanks abunch!
Edit: When I ran the debugger, my program continously throws exceptions whenever the array is refrenced.
As stated in the video-clip continuing with 1 will end in an endless loop. Try the following.
static int[] collatzCounts = new int[100];
static final int NO_COUNT = -1;
static {
Arrays.fill(collatzCounts, NO_COUNT);
collatzCounts{1] = 0; // Define collatz(1) = 0 (1, 4, 2, 1, ...)
}
public static void main(String[] args) {
for (int n = 2; n < 120; n++) {
int steps = countCollatz(n);
System.out.println(n + ": " + steps);
}
}
public static int countCollatz(int n) {
IntFunction f = k ->
k % 2 == 0
? 1 + countCollatz(k / 2)
: 1 + countCollatz(3 * k + 1);
//: 2 + countCollatz((3 * k + 1) / 2);
//if (n == 1) {
// return 0;
//}
if (n < collatzCounts.length) {
if (collatzCounts[n] == NO_COUNT) {
collatzCounts[n] = f.apply(n);
}
return collatzCounts[n];
} else {
return f.apply(n);
}
}
countCollatz simply counts the steps needed - to reach 1 actually. Though till further proof there might be a cycle of higher numbers.
I have used a Java 8 lambda expression, the IntFunction f, as it is more natural to repeat the calculation, once to fill the array, once for too large numberss.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments