学习Java -不要完全理解这个序列是如何计算的(斐波纳契)

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

首先，我必须告诉您，这个递归版本具有惊人的指数代价。一旦您了解了它的工作原理，我对您的建议将是学习尾递归，编写一个tail-recursive解决方案，一个迭代解决方案，并将它们与当前的“数字”值较高的方法进行比较。

然后，您的函数基本上使用Fibonacci序列的数学定义：

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“很高时，它就有了价值。