Java递归Fibonacci序列?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (68)

请解释这段代码

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

我对最后一行感到困惑,请详细解释一下!

提问于
用户回答回答于

在Fibonacci序列中,每一项都是前两项的和。所以,你写了一个递归算法。

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 elementFibonacci序列返回5...

用户回答回答于

代码有两个问题:

  1. 结果存储在int中,它只能处理前48个斐波那契数,之后整数填充减号和结果是错误的。
  2. 但是你永远不能运行Fibonacci(50)。 密码fibonacci(n - 1) + fibonacci(n - 2)是非常错误的。 问题是它叫斐波纳契的次数不是50次,而是更多。 最初它调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;
}

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励