为什么我的递归斐波那契实现是用 C++ 编写的？段错误？

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

Answer 1

当 x==2 调用 fib(1) 和 fib(0) 时：

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

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

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。

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;
}

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));
}

Answer 5

我认为这个解决方案很短，看起来不错：

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）

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

Answer 6

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

在斐波那契数列中，前 2 个数字总是紧随 1，然后每次该值变为 1 或 2 时，它必须返回 1

Answer 7

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

#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;
}