斐波那契数的递归函数

Question

我要写一个简单的程序如下："Given a non-negative integer n, find the nth Fibonacci number using recursion"。我认为这意味着，对于用户输入的任何值，我都必须得到斐波那契数。例如，如果用户输入 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;
}

Answer 1

你的递归停止条件在它之外，在下面的 if 中：

if (userValue == 1 || userValue == 0) {...}

但它应该在 fib 函数中。

你目前拥有的是无限递归，这是堆栈溢出的最短路径。

Answer 2

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

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

在你的情况下，

假设 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 不存在，应该提供终止条件，这样递归就会停止，return 结果。

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

 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

希望这对您有所帮助。谢谢。

Answer 3

上面代码中的递归永远不会停止，只有当堆栈已满导致程序终止运行时才会停止。为你编程：

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

斐波那契数的递归函数

Recursive function for Fibonacci number

c++

recursion

fibonacci

c++11