Fibonacci函数问题
Fibonacci函数问题
提问于 2010-05-02 04:38:02
我在计算斐波那契数列时，偶然发现了这段代码，我经常看到：
int Fibonacci (int x)
{
if (x<=1) {
return 1;
}
return Fibonacci (x-1)+Fibonacci (x-2);
}我不明白的是它是如何工作的，特别是最后的返回部分:它会再次调用斐波那契函数吗？有没有人能给我介绍一下这个函数？
回答 8
Stack Overflow用户
回答已采纳
发布于 2010-05-02 04:55:47
是的，该函数调用自身。例如,
Fibonacci(4)
= Fibonacci(3) + Fibonacci(2)
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0))
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1)
= ((1 + 1) + 1) + 2
= (2 + 1) + 2
= 3 + 2
= 5注意，Fibonacci函数在这里被调用了9次。一般来说，朴素的递归fibonacci函数有exponential running time，这通常是件坏事。
Stack Overflow用户
发布于 2010-05-02 04:39:16
这是一个经典的recursive function示例，它是一个调用自身的函数。
如果你仔细阅读它，你会看到它会一次又一次地调用它自己，或者，递归，直到它达到所谓的基本情况，当x <= 1在这一点上开始“回溯”并对计算值求和。
下面的代码清楚地打印出算法的轨迹：
public class Test {
static String indent = "";
public static int fibonacci(int x) {
indent += " ";
System.out.println(indent + "invoked with " + x);
if (x <= 1) {
System.out.println(indent + "x = " + x + ", base case reached.");
indent = indent.substring(4);
return 1;
}
System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2));
int retVal = fibonacci(x-1) + fibonacci(x-2);
System.out.println(indent + "returning " + retVal);
indent = indent.substring(4);
return retVal;
}
public static void main(String... args) {
System.out.println("Fibonacci of 3: " + fibonacci(3));
}
}输出如下：
invoked with 3
Recursing on 2 and 1
invoked with 2
Recursing on 1 and 0
invoked with 1
x = 1, base case reached.
invoked with 0
x = 0, base case reached.
returning 2
invoked with 1
x = 1, base case reached.
returning 3
Fibonacci of 3: 3该轨迹的树描述将如下所示
fib 4
fib 3 + fib 2
fib 2 + fib 1 fib 1 + fib 0
fib 1 + fib 0 1 1 1
1 1编写递归函数时需要考虑的重要部分是：
1.处理基本情况
如果我们在上面的例子中忘记了if (x<=1) return 1;，会发生什么呢？
2.确保递归调用以某种方式减少到基本情况
如果我们意外地修改了算法以返回fibonacci(x)+fibonacci(x-1);，会发生什么情况
Stack Overflow用户
发布于 2010-05-02 05:05:10
返回Fibonacci (x-1)+Fibonacci (x-2)；
这是非常低效的。我建议使用以下线性替代方案：
unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c)
{
return (n == 2) ? c : fibonacci(n - 1, b, c, b + c);
}
unsigned fibonacci(unsigned n)
{
return (n < 2) ? n : fibonacci(n, 0, 1, 1);
}fibonacci数列可以用函数式语言更简洁地表示。
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)
> take 12 fibonacci
[0,1,1,2,3,5,8,13,21,34,55,89]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2751458
复制相关文章
相似问题
腾讯云开发者
