logo标签列表

递归斐波那契数列

c++recursionfibonacci
36

我很难理解为什么

#include <iostream>

using namespace std;

int fib(int x) {
    if (x == 1) {
        return 1;
    } else {
        return fib(x-1)+fib(x-2);
    }
}

int main() {
    cout << fib(5) << endl;
}

导致分段错误。一旦x降到1，它不应该最终返回吗？

14
该算法的时间复杂度为O(2^n)，非常低效。例如，计算f(30)需要约10亿次操作。建议使用动态规划来优化。 - Alexey Malistov
5
@Alexey，我相信原帖只是想学习。如果性能是一个问题，元编程确实是一种不错的选择。 - LiraNuna
2
@Alexey Malistov：不，改用迭代方法。 - Gumbo
11
@Gumbo：不，使用原力卢克！ - Spoike
21
我喜欢开玩笑（或者不是开玩笑）说这个算法的时间复杂度是O(fib(n))。 - R. Martinho Fernandes
显示剩余2条评论
13个回答
0

我认为所有这些解决方案都是低效的。它们需要大量的递归调用才能获得结果。

unsigned fib(unsigned n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

这段代码需要14次调用才能得到fib(5)的结果，177次调用才能得到fib(10)的结果，而要得到fib(30)的结果则需要2.7kk次调用。

你最好使用this方法，或者如果想要使用递归，请尝试以下方法：

unsigned fib(unsigned n, unsigned prev1 = 0, unsigned prev2 = 1, int depth = 2)     
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    if(depth < n) return fib(n, prev2, prev1+prev2, depth+1);
    return prev1+prev2;
}

这个函数需要进行n次递归调用来计算斐波那契数列的第n项。你仍然可以通过调用fib(10)来使用它，因为所有其他参数都有默认值。

0

我的解决方案是：

#include <iostream>


    int fib(int number);

    void call_fib(void);

    int main()
    {
    call_fib();
    return 0;
    }

    void call_fib(void)
    {
      int input;
      std::cout<<"enter a number\t";
      std::cin>> input;
      if (input <0)
      {
        input=0;
        std::cout<<"that is not a valid input\n"   ;
        call_fib();
     }
     else 
     {
         std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
     }

    }





    int fib(int x)
    {
     if (x==0){return 0;}
     else if (x==2 || x==1)
    {
         return 1;   
    }

    else if (x>0)
   {
        return fib(x-1)+fib(x-2);
    }
    else 
     return -1;
    }

它返回fib(0)=0，如果是负数则返回错误。

0

我认为使用递归是斐波那契数列的最佳解决方案。

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
ull FIBO[100005];
using namespace std;
ull fibo(ull n)
{
    if(n==1||n==0)
        return n;
    if(FIBO[n]!=0)
        return FIBO[n];
    FIBO[n] = (fibo(n-1)+fibo(n-2));
    return FIBO[n];
}
int main()
{
    for(long long  i =34;i<=60;i++)
        cout<<fibo(i)<<" " ;
    return 0;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接