递归法时间复杂度高，仅适合理解；推荐使用迭代法，时间复杂度O(n)、空间O(1)；动态规划通过记忆化避免重复计算，适合多次查询场景。
实现斐波那契数列在C++中有多种方式，常见的有递归、循环（迭代）和动态规划。每种方法各有特点，适用于不同场景。
1. 递归实现（简单但效率低）
适合理解逻辑，但时间复杂度为 O(2^n)，存在大量重复计算。代码如下：
#include
using namespace std;
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
int n = 10;
cout << "第 " << n << " 项是：" << fib(n) << endl;
return 0;
}
2. 迭代实现（推荐，效率高）
时间复杂度 O(n)，空间复杂度 O(1)，适合大数值计算。使用两个变量保存前两项的值，逐项推进：
立即学习“C++免费学习笔记（深入）”；
#include
using namespace std;
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
c = a + b;
a = b;
b = c;
}
return b;
}
int main() {
int n = 10;
cout << "第 " << n << " 项是：" << fib(n) << endl;
return 0;
}
3. 动态规划（记忆化递归）
结合递归思想与缓存机制，避免重复计算。用数组保存已计算的结果：
#include
using namespace std;
int fibHelper(int n, int* memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
return memo[n];
}
int fib(int n) {
int* memo = new int[n + 1];
fill(memo, memo + n + 1, -1); // 初始化为-1
int result = fibHelper(n, memo);
delete[] memo;
return result;
}
int main() {
int n = 10;
cout << "第 " << n << " 项是：" << fib(n) << endl;
return 0;
}
总结： 对于实际应用，推荐使用迭代法，它效率高且不易栈溢出。递归仅用于教学演示。若需多次查询，可考虑预打表或记忆化优化。
基本上就这些，不复杂但容易忽略性能差异。
