java - Java递归斐波那契序列

请解释以下简单代码:

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的值方法。请详细解释!

最佳答案

在斐波那契数列中，每一项都是前两项的总和。因此，您编写了一个递归算法。

所以，

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 element，斐波那契序列返回5。

看到这里Recursion Tutorial。

关于java - Java递归斐波那契序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8965006/