斐波那契数列定义为F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）；简单递归效率低，存在大量重复计算；记忆化递归通过存储已计算值将时间复杂度降为O(n)；迭代法最优，时间O(n)，空间O(1)，适合大数值计算。
斐波那契数列是一个经典的递归问题，数列定义为：第0项是0，第1项是1，从第2项开始，每一项都等于前两项之和。即：
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（当 n ≥ 2）
简单递归实现
最直观的写法是使用递归函数：
#includeusing namespace std; int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); }
int main() { int n = 10; cout << "F(" << n << ") = " << fibonacci(n) << endl; return 0; }
这个版本代码简洁，但效率很低，因为存在大量重复计算。例如计算 F(5) 时，F(3) 会被多次重复调用。
立即学习“C++免费学习笔记（深入）”；
优化方案：记忆化递归
为了避免重复计算，可以用数组记录已经算过的值：
#include#include using namespace std; int fib_memo(int n, vector
& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo); return memo[n]; } int fibonacci_memo(int n) { vector
memo(n + 1, -1); return fib_memo(n, memo); } int main() { int n = 10; cout << "F(" << n << ") = " << fibonacci_memo(n) << endl; return 0; }
这样每个值只计算一次，时间复杂度降到 O(n)，空间换时间。
更高效的迭代方法（推荐）
虽然题目要求递归，但实际应用中迭代更高效：
#includeusing namespace std; int fibonacci_iterative(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 << "F(" << n << ") = " << fibonacci_iterative(n) << endl; return 0; }
时间 O(n)，空间 O(1)，适合大数值计算。
基本上就这些。递归写法容易理解，但要注意性能问题。小数据可用记忆化，大数据建议用迭代。不复杂但容易忽略效率陷阱。
