Java递归Fibonacci序列 [英] Java recursive Fibonacci sequence

问题描述

请解释这个简单的代码：

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，例如，然后将调用斐波那契（4）+斐波那契（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!

推荐答案

您的代码有2个问题：

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


2. 但是你永远不能运行斐波那契（50）。
   
   代码
   
   斐波那契（n - 1）+斐波那契（n - 2）
   
   是非常错误的。
   
   问题在于它称斐波纳契不是50倍而是更多。
   
   起初它叫斐波那契（49）+斐波那契（48），
   
   next斐波那契（48）+斐波那契（47）和斐波那契（47）+斐波那契（46）
   
   每次变得斐波那契（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递归Fibonacci序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！