时间戳

首页 > 解决方案 > 斐波那契数的递归函数

c++ - 斐波那契数的递归函数

问题描述

我必须编写一个简单的程序，如下所示：“给定一个非负整数 n，使用递归找到第 n 个斐波那契数”。我认为这意味着，对于用户输入的任何值，我都必须得到斐波那契数。例如，如果用户输入 4，我将不得不获取斐波那契数列中的第 4 个值（即 2）。下面是我写的内容，但是我的递归有问题，因为它在我运行它时会崩溃。感谢任何帮助...

int userValue;
int fibo;
int fib(int n);
int fibValue;


int main() {
    cout << "Please provide your value" << endl;
    cin >> userValue;

    while (userValue < 0) {
        cout << "Fibonacci numbers only start at 0, please try again: " << endl;
        cin >> userValue;
    }

    if (userValue == 1 || userValue == 0) {
        cout << "Fibonacci result is: " << userValue << endl;
        return 0;
    }
    else {
        fib(userValue);
        cout << "Fibonacci result is: " << fibValue << endl;
        //return 0;
    }
}

int fib(int n)
{
    fibValue = fib(n - 1) + fib(n - 2);
    return fibValue;
}

标签： c++c++11recursionfibonacci

解决方案

问题出在fib方法上。没有提供终止条件。因此，递归将在循环中发生而不会终止。

首先，尝试通过提供多个输入来调试任何问题，您将了解问题所在。

在你的情况下，

对于假设n=3，

跟踪将是这样的

fib(3) -> which further invokes fib(2) and fib(1)

fib(2) -> which further invokes fib(1) and fib(0)

现在因为没有终止条件

fib(0) will further invoke fib(-1) and fib(-2)

由于负值 fib 不存在终止条件，因此应提供递归停止并返回结果。

对于斐波那契数，终止条件如下：

 if(n == 0){
  return 0;
 }else if (n == 1){
  return 1;
 }

很少参考

https://blog.hartleybrody.com/debugging-code-beginner/

https://www.codementor.io/mattgoldspink/how-to-debug-code-efficiently-and-effectively-du107u9jh%60

希望这可以帮助。谢谢。

推荐阅读