Java 递归斐波那契数列

java recursion fibonacci

2022-08-31 07:11:36

请解释这个简单的代码：

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，那么会调用斐波那契（4）+斐波那契（3）等等，但我不明白这个算法如何通过这种方法计算指数5处的值。请详细解释！

答案 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 element5

请参阅此处了解递归教程。

答案 2

您的代码存在 2 个问题：

结果存储在 int 中，只能处理前 48 个斐波那契数列，在此之后，整数填充减去位，结果是错误的。
但你永远不能运行斐波那契（50）。
代码

非常错误。
问题是，它调用斐波那契不是50次，而是更多。
起初它调用斐波那契（49）+斐波那契（48），
下一个斐波那契（48）+斐波那契（47）和斐波那契（47）+斐波那契（46）
每次它变得更差，所以复杂性是指数级的。fibonacci(n - 1) + fibonacci(n - 2)

非递归代码的方法：

 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;
}