Collatz猜想递归错误

Question

我潜伏了很多年，但今天我有一个关于我的代码的问题。我目前正在尝试创建一个 collatz 程序，该程序将某个数字的步数放入一个数组中，但同时将它通过的每个数字的步数都放在一起。这是我的代码：

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

这是关于 Collatz 猜想的精彩视频：Numberphile

这里是抛出的错误（减少），但我不明白，因为我不在任何 int 或 short 的边界附近：

Exception in thread "main" java.lang.WhosebugError
at GenerousRecursion.findCollatz(GenerousRecursion.java:22)
at GenerousRecursion.findCollatz(GenerousRecursion.java:33)
at GenerousRecursion.findCollatz(GenerousRecursion.java:27)

我只列出了前三行，因为这三行绘制了数百行错误。

有什么问题，我该如何解决？谢谢大家！

编辑：当我运行调试器时，只要引用数组，我的程序就会不断抛出异常。

Answer 1

如视频中所述，继续 1 将无限循环结束。请尝试以下操作。

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 只是计算实际达到 1 所需的步数。虽然直到进一步证明可能会有一个更高数字的循环。

我使用了 Java 8 lambda 表达式，IntFunction f，因为它更自然地重复计算，一次填充数组，一次用于太大的数字。

Collatz猜想递归错误

Collatz Conjecture Recursion Error

java

stack-overflow

arrays

collatz

Collat​​z猜想递归错误

Collatz Conjecture Recursion Error

java

stack-overflow

arrays

collatz

Collatz猜想递归错误