使用 BigInteger 的斐波那契数列不产生答案

Question

我要找到斐波那契数列的第 100 个元素，我最初尝试使用 int 存储数字值，但它溢出并切换为负值，就像 long.
然后我遇到了 BigInteger 我确实使用一个简单的 for 循环和一个 array 来存储结果并访问前面的元素得到了解决方案。
现在作为我正在尝试使用 recursion 解决同样的问题该程序似乎没有终止。我在这里错过了什么吗？或者 BigInteger 不建议与递归一起使用？

代码如下：

import java.math.BigInteger;

class Test {
  public static void main(String[] args) {
    BigInteger n = BigInteger.valueOf(100);
    System.out.println(fib(n));
  }

  public static BigInteger fib(BigInteger n) {
    if (n.compareTo(BigInteger.valueOf(1)) == 0 || n.compareTo(BigInteger.valueOf(1)) == -1)
      return n;
    return fib(n.subtract(BigInteger.valueOf(1))).add(fib(n.subtract(BigInteger.valueOf(2))));
  }
}

Answer 1

在评论中，您提到您认为程序不会终止的假设是基于它运行超过 5 分钟的事实。那是不是证明非终止的方式。

如果您在一定时间内观察到程序终止，那么您可以得出结论，它确实终止了。但是，如果您没有观察到它在一定时间内终止，那么您可以准确地说nothing它是否终止。等久一点可能会终止，等久了可能会终止，甚至理论上可能会终止，但比宇宙的热寂还要长。

在您的特定情况下，算法是完全正确的，并且它总是会终止。它根本不是一个非常有效的算法：为了计算 fib(n)，fib 被调用 fib(n) 次，因为你一遍又一遍地计算相同的数字。

如果我们假设您可以每个时钟周期执行一次 fib（这是一个乐观的假设，因为对 fib 的一次调用执行一个条件、两次减法、一次加法和两次调用在大多数情况下到 fib，并且一次添加可能已经需要多个时钟周期，具体取决于 CPU），我们进一步假设您有一个 100 核心 CPU 并且您的代码实际上是并行执行，并且您有 100 CPUs，每个 CPU 的时钟频率为 100 GHz，并且您有一个由 100 台计算机组成的集群，那么它将 still 大约需要一个小时。

在一些更现实的假设下，您的程序完成所花费的时间大约为数万年。

由于您的代码未并行化，为了让您的代码在更现实的 4 GHz CPU 上在 5 分钟内完成，它需要执行 fib 将近 300 百万次每个时钟周期。

对代码的预期性能进行一些非常粗略的猜测通常会有所帮助。如您所见，您不需要成为 Java 或 JVM、编译器、优化或计算机组织或 CPU 设计或性能工程方面的专家。您不需要确切地知道您的代码被编译成什么。您不需要知道一个整数 ADD 需要多少个时钟周期。因为甚至当你做出一些 完全过分荒谬的 假设时，你仍然可以很容易地看到你的代码 不可能 在几分钟甚至几小时内完成。

使用 BigInteger 的斐波那契数列不产生答案

Fibonacci sequence using BigInteger Does not yield an answer

java

recursion

fibonacci