递归斐波那契

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

原因是因为Fibonacci序列以两个已知实体0和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

根据定义,Fibonacci序列中的前两个数字是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));
}