Java递归斐波那契数列

问题描述

请解释一下这个简单的代码:

Please explain this simple code:

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 用这个方法.请详细解释！

I'm confused with the last line especially because if n = 5 for example, then fibonacci(4) + fibonacci(3) would be called and so on but I don't understand how this algorithm calculates the value at index 5 by this method. Please explain with a lot of detail!

推荐答案

您的代码有两个问题:

1. 结果存储在 int 中，它只能处理前 48 个斐波那契数，在此之后整数填充减去位并且结果是错误的.
2. 但你永远无法运行 fibonacci(50).
   代码
   斐波那契(n - 1) + 斐波那契(n - 2)
   大错特错.
   问题是它调用的斐波那契数不是 50 次，而是更多.
   起初它调用 fibonacci(49)+fibonacci(48),
   下一个斐波那契(48)+斐波那契(47) 和斐波那契(47)+斐波那契(46)
   每次它变得 fibonacci(n) 更糟，所以复杂性是指数级的.

非递归代码的方法:

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

这篇关于Java递归斐波那契数列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！