学习Java-不完全了解此序列的计算方式（Fibonacci）

Question

我正在学习Java，并且可以从网上获得以下代码并在Eclipse中运行它：

public class Fibonacci {

    public static void main (String [] args) { 
        for (int counter = 0; counter <= 3; counter++){
            System.out.printf("Fibonacci of %d is: %d\n",  counter, fibonacci(counter));

    }

    public static long fibonacci(long number) {
        if ((number == 0) || (number == 1))
             return number;
        else
             return fibonacci(number - 1) + fibonacci(number - 2);
    }
}

我试图理解它，但无法理解。因此，我遍历了代码并counter通过了fibonacci方法。计数器开始于0，这是首先传递的内容，然后1，我了解了该方法0随后传递的原因1。

当达到2时： 它将返回2-1 + 2-2 = 2并且确实返回此值。
当达到3时： 它将返回，3-1 + 3-2 = 3但不返回，3它将返回2。

请有人可以向我解释为什么我无法弄清楚吗？

谢谢

Answer 1

首先，我必须告诉您， 此递归版本具有巨大的指数成本 。一旦了解了它的工作原理，对您的建议就是学习尾部递归性，编写 尾部递归 解决方案，
迭代 解决方案，并将它们与当前方法进行比较，以获取较高的“数字”值。

然后，您的函数基本上使用斐波那契数列的数学定义：

f0 = 1, f1 = 1, fn = fn-1 + fn-2 for all n >= 2

例如，如果我们调用fibonacci（3），则将返回fibonacci（2）+
fibonacci（1）。fibonacci（2）将首先执行，并返回fibonacci（1）+
fibonnacci（0）。然后fibonacci（1）将立即返回1，因为它是一个终止情况。与fibonnacci（0）发生的事情相同，因此现在我们计算出fibonnacci（2）=
1 + 0 =1。让我们回到fibonacci（3），它在这一点上已经部分评估：1 + fibonnacci（1）
。我们只需要计算fibonnacci（1）就可以最终返回1 +1 = 2。

即使在这个小例子中，您也可以看到我们对fibonacci（1）进行了两次评估，这就是为什么该版本是如此之慢，它多次计算相同序列值的原因，并且当“
number”很高时就很有价值。