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

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

2023-06-30 14:11:29 深夜i -- --

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

斐波那契数列可能是最经典的递归算法之一，其定义为下一个数字是前两个数字之和。使用C++可以很容易地实现这个递归算法。

斐波那契数列递归算法的核心是递归函数，它接收一个整数参数n表示要计算的斐波那契数列的项数。该算法的基本情况是n等于0或1时直接返回n。对于其他情况，递归函数将调用自身两次，分别计算n-1和n-2的斐波那契数并将它们相加。

下面是斐波那契数列递归算法的C++实现：


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

测试斐波那契数列递归算法非常简单，只需要调用函数并传入一个整数参数n来指定计算的项数。下面是一个示例程序，它打印前10项斐波那契数列：


#include <iostream>
using namespace std;
int fib(int n) {
  if (n == 0 || n == 1)
    return n;
   else {
    return fib(n-1) + fib(n-2);
  }
}
int main() {
  for (int i = 0; i < 10; i++) {
    cout << fib(i) << " ";
  }
  return 0;
}

该程序将输出：0 1 1 2 3 5 8 13 21 34

斐波那契数列递归算法的时间复杂度非常高，以指数速度增长。这意味着随着计算项数的增加，算法的运行时间将快速增加。如果您需要计算大量的斐波那契数，建议使用其他策略，例如迭代或基于矩阵的方法。

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

下一篇: 学习C++，VS2019安装应该勾选哪些选项？

评论区

()

相似文章