c++ - 我试图用 C++ 编写递归斐波那契数列，但是当我编译时出现错误

Question

当我尝试在 C++ 中使用递归算法计算斐波那契数列时，我收到有关内存分配的错误。我可以运行具有 void 返回值的递归算法，但是当返回值是 int 时，内存就会出现问题。有解决办法吗？

#include <iostream>
using namespace std;

int fib(int start);

int main()
{
  int x,y;
  cout << "Enter a value for x: ";
  cin >> x;


  y = fib(x);
  cout << "Your product is: ";
  cout << y << endl;
  return 0;

}

int fib(int start){
  if(start == 0 || start == 1){
    return start;
  }
  return fib(start)*fib(start-1);
}

Answer 1

问题是斐波那契函数不对...

如果您的变量 start 恰好不同于 0 或 1，那么您可以反复执行 fib(start) 函数

return fib(start)*fib(start-1);

这将产生一个 stackoverflow，因为该函数正在无限地调用自身。

另一方面，您不应将这些值相乘，而应将其相加

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