递归斐波那契数列

Question

我很难理解为什么

#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，它不应该最终返回吗？

- Ian Burris

---

该算法的时间复杂度为O(2^n)，非常低效。例如，计算f(30)需要约10亿次操作。建议使用动态规划来优化。 - Alexey Malistov

@Alexey，我相信原帖只是想学习。如果性能是一个问题，元编程确实是一种不错的选择。 - LiraNuna

@Alexey Malistov：不，改用迭代方法。 - Gumbo

@Gumbo：不，使用原力卢克！ - Spoike

我喜欢开玩笑（或者不是开玩笑）说这个算法的时间复杂度是O(fib(n))。 - R. Martinho Fernandes

Answer 1

当 x==2 时，你会调用 fib(1) 和 fib(0):

return fib(2-1)+fib(2-2);

考虑当评估fib(0)时会发生什么...

- Georg Fritzsche

---

+1 是因为没有直接给出答案，而是提示问题所在。对于正在学习的人来说更好。 - Xetius

+1，我用相同的技巧来教我的大儿子（9岁），这激发了他解决问题的能力。 - Toon Krijthe

Answer 2

原因是斐波那契数列以两个已知实体0和1开头。你的代码只检查了一个（即1）。

将你的代码改为

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

要包括0和1。

- LiraNuna

---

这个系列难道不是从1,1开始吗？ - vpram86

这不是我所学的，也不是维基百科所建议的 - http://en.wikipedia.org/wiki/Fibonacci_number - LiraNuna

@Aviator: 取决于你如何定义斐波那契数列。 ;) - Spoike

可以将两行代码改为 if (x <= 1) return x。 :-) - ghostmansd

或者改为 if (x<2)。 - Abhinav Gauniyal

Answer 3

为什么不使用迭代算法？

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

- Dzmitry Huba

---

那是最好的方法。但他要求一个递归解决方案。 - Gumbo

@Gumbo，最好的方法无疑是元编程。 - LiraNuna

“元编程方法基本上可以归结为递归解决方案......计算将简单地从运行时转移到编译时。声称这是一个更好的方法是无意义的，因为我们不知道操作者的要求：如果他只需要运行程序一次，那么具有巨大的编译时间和短暂的运行时间并不比具有短暂的编译时间和长时间的运行时间更好。同样，如果他需要以“n”参数作为输入，则元编程无法使用（除非您在此数字上明确设置了上限）。此外，编译器具有有限的...” - Luc Touraille

递归深度可能会成为一个问题，因此这可能是一个问题。总之，元编程是一个非常强大的工具，但应该明智地使用，只有在它真正适合解决问题时才使用。 - Luc Touraille

为了OP的利益，必须说：在99%的实际情况下，迭代运行时解决方案是唯一的选择。迭代解决方案比错误的递归模板解决方案要快得多。与正确的递归模板解决方案相比，速度要慢得多。https://wandbox.org/permlink/43Gb20ACqmvQHdhT - user10133158

Answer 4

根据定义，斐波那契数列的前两个数字是1和1，或者是0和1。因此，你需要处理它。

#include <iostream>
using namespace std;

int Fibonacci(int);

int main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}

int Fibonacci(int x) 
{
    if (x < 2){
     return x;
    }     
    return (Fibonacci (x - 1) + Fibonacci (x - 2));
}

- Vanji

Answer 5

这是我使用递归解决斐波那契问题的方法。

#include <iostream>
using namespace std;

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

int main() {
    cout << fibonacci(8);
    return 0;
}

- Pedro Eugénio

Answer 6

我认为这个解决方案简洁而美观:

long long fib(int n){
  return n<=2?1:fib(n-1)+fib(n-2);
}

编辑：正如jweyrich所提到的，真正的递归函数应该是：

long long fib(int n){
      return n<2?n:fib(n-1)+fib(n-2);
    }

(因为 fib(0) = 0。但根据上述递归公式，fib(0) 应该是 1)

要理解递归算法，你应该在纸上画图，并且最重要的是：经常“正常思考”。

- hqt

---

fib(0) 错误地结果为 1。这个问题可以通过使用以下代码解决: return x < 2 ? x : fibonnaci(x-1) + fibonnaci(x-2);。在这里，专为 fib(2) 设计的额外条件只会减慢函数运行速度。 - jweyrich

通常斐波那契函数n只会递归调用到大约50。我认为额外的条件不会减慢递归调用的速度。 - hqt

我的意思是你的fib函数在fib(0)上返回了错误的结果。请忽略其余部分 :-) - jweyrich

Answer 7

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

在斐波那契数列中，前两个数字始终为1，然后每次值变为1或2时，必须返回1。

- noelyahan

Answer 8

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

- user2331083

---

你对这个问题有答案吗？（请参见下面的为什么） - Trinimon

Answer 9

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

- zod

---

太好了！我刚刚删除了else。 - Avelino

Answer 10

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

然而，使用递归获取斐波那契数列并不是一个好的实践，因为函数被调用的次数约为接收到的数字的8.5倍。例如，要获取第30个斐波那契数（1346269）- 函数将被调用7049122次！

- Jokerius