Java递归斐波那契序列

Question

请解释以下简单代码：public int fibonacci(int n)  {    if(n == 0)        return 0;    else if(n == 1)      return 1;   else      return fibonacci(n - 1) + fibonacci(n - 2);}我对最后一行感到困惑，尤其是因为例如，如果n = 5，则将调用fibonacci（4）+ fibonacci（3），依此类推，但我不明白该算法如何以此来计算索引5的值方法。请详细解释！

Answer 1

在斐波那契数列中，每一项都是前两项的总和。因此，您编写了一个递归算法。

所以，

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

现在您已经知道了fibonacci(1)==1 and fibonacci(0) == 0。因此，您可以随后计算其他值。

现在，

fibonacci(2) = 1+0 = 1

fibonacci(3) = 1+1 = 2

fibonacci(4) = 2+1 = 3

fibonacci(5) = 3+2 = 5

从斐波那契数列中0,1,1,2,3,5,8,13,21....我们可以看到5th element斐波那契数列返回了5。

Answer 2

您的代码有2个问题：

结果存储在只能处理前48个斐波那契数字的int中，此后整数填充减位，结果是错误的。

但是您永远无法运行fibonacci（50）。

该代码

fibonacci(n - 1) + fibonacci(n - 2)

是非常错误的。

问题是它调用斐波那契的次数不是50次，而是更多次。

首先，它 每次调用fibonacci（n）越差，就称为fibonacci（49）+ fibonacci（48），

其次称为fibonacci（48）+ fibonacci（47）和fibonacci（47）+ fibonacci（46）

，因此复杂度是指数级的。 

非递归代码的方法：

 double fibbonaci(int n){

    double prev=0d, next=1d, result=0d;

    for (int i = 0; i < n; i++) {

        result=prev+next;

        prev=next;

        next=result;

    }

    return result;

}

Answer 3

在伪代码中，其中n = 5，将发生以下情况：

斐波那契（4）+斐波那契（3）

这可分为：

（fibonacci（3）+ fibonnacci（2））+（fibonacci（2）+ fibonnacci（1））

这可分为：

（（（fibonacci（2）+ fibonnacci（1））+（（（fibonacci（1）+ fibonnacci（0）））+（（（（fibonacci（1）+ fibonnacci（0））+ 1）））

这可分为：

（（（（fibonacci（1）+ fibonnacci（0））+1）+（（1 + 0））+（（1 + 0）+1）））

这可分为：

（（（（（1 + 0）+1）+（（1 + 0））+（（1 + 0）+1）））

结果是：5

给定fibonnacci序列为1 1 2 3 5 8 ...，第5个元素为5。您可以使用相同的方法来计算其他迭代。