C++实现斐波那契数列的普通递归算法 |21xrx.com

C++实现斐波那契数列的普通递归算法

2023-07-10 21:47:33 深夜i -- --

C++ 斐波那契数列普通递归算法

斐波那契数列是指从0开始，第0项为0，第1项为1，从第三项开始，每一项都是前两项之和的数列。其前几项为：0，1，1，2，3，5，8，13，21，34，……

在C++中，可以使用普通递归算法来实现斐波那契数列。普通递归算法是指函数自己调用自己，通过递归来求解问题的方法。

下面是一段C++代码，用来实现斐波那契数列的普通递归算法：


#include <iostream>
using namespace std;
int fibonacci(int n)
{
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
  int n;
  cout << "请输入要输出的斐波那契数列的项数：";
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cout << fibonacci(i) << " ";
  }
  cout << endl;
  return 0;
}

在上面的代码中，fibonacci()函数接受一个整数参数n，表示要计算的斐波那契数列的第n项，返回值为计算结果。如果n为0或1，直接返回0或1，因为此时的斐波那契数列的第0项和第1项已知。当n大于1时，使用递归调用fibonacci()函数来计算第n项的值。具体的实现方法是，递归调用fibonacci(n-1)和fibonacci(n-2)，然后将它们的返回值相加，得到第n项的值。

在main()函数中，首先要输入要输出的斐波那契数列的项数n。然后使用一个for循环来依次输出前n项的斐波那契数列。

需要注意的是，虽然普通递归算法实现斐波那契数列非常简洁，但它存在严重的效率问题。由于递归的特点，每次递归调用都会带来额外的堆栈空间和调用时间，因此当n很大时，计算斐波那契数列的时间将急剧增加。在这种情况下，应该使用其他更高效的算法来实现斐波那契数列。

上一篇: idea打包java可执行jar包

下一篇: VSCode C++ 编辑器出现乱码问题？这里有解决方法！

评论区

()

相似文章