请解释一下这个简单的代码:
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的值的。请详细解释一下!
发布于 2012-01-23 05:56:37
在斐波那契数列中,每一项都是前两项的总和。所以,你写了一个递归算法。
所以,
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
从斐波那契数列,我们可以看到,对于5th element
,斐波那契数列返回5
。
有关Recursion Tutorial的信息,请参阅此处。
发布于 2015-11-25 05:37:25
您还可以简化您的函数,如下所示:
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
发布于 2012-01-23 06:08:00
递归有时很难掌握。只需在一张纸上对一个小数字进行评估:
fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3
我不确定Java实际上是如何评估这一点的,但结果将是相同的。
https://stackoverflow.com/questions/8965006
复制相似问题