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 = 1fibonacci(3) = 1+1 = 2fibonacci(4) = 2+1 = 3fibonacci(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），因此复杂度是指数级的。&nbsp;非递归代码的方法：&nbsp;double fibbonaci(int n){&nbsp; &nbsp; double prev=0d, next=1d, result=0d;&nbsp; &nbsp; for (int i = 0; i < n; i++) {&nbsp; &nbsp; &nbsp; &nbsp; result=prev+next;&nbsp; &nbsp; &nbsp; &nbsp; prev=next;&nbsp; &nbsp; &nbsp; &nbsp; next=result;&nbsp; &nbsp; }&nbsp; &nbsp; 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。您可以使用相同的方法来计算其他迭代。