斐波那契数列在C++中可通过递归实现，但基础递归存在重复计算问题，时间复杂度为O(2^n)；通过记忆化递归引入缓存可将时间复杂度降至O(n)；尾递归形式通过传递状态参数减少栈深度，提升效率；实际应用中可根据需求选择递归或迭代方式。
在C++中，斐波那契数列是一个经典的递归应用场景。数列定义为：F(0) = 0，F(1) = 1，且当 n ≥ 2 时，F(n) = F(n-1) + F(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) 会被多次调用，导致时间复杂度达到 O(2^n)，效率极低。
优化技巧：记忆化递归
为了避免重复计算，可以引入一个数组或哈希表来缓存已经计算过的值，这种方法称为“记忆化递归”（Memoization）。
立即学习“C++免费学习笔记（深入）”；
#include#include using namespace std; int fib_helper(int n, vector
& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib_helper(n - 1, memo) + fib_helper(n - 2, memo); return memo[n];}
int fibonacci(int n) { vector
memo(n + 1, -1); // 初始化为-1表示未计算 return fib_helper(n, memo); }
通过缓存中间结果，时间复杂度降低到 O(n)，空间复杂度为 O(n)，显著提升了性能。
进一步优化：尾递归尝试
C++ 不直接支持尾递归优化，但我们可以通过修改递归形式，模拟尾递归思路，减少调用栈深度。
int fibonacci_tail(int n, int a = 0, int b = 1) {
if (n == 0)
return a;
if (n == 1)
return b;
return fibonacci_tail(n - 1, b, a + b);
}
这种写法将状态作为参数传递，避免了多路递归，虽然编译器不一定优化为循环，但逻辑更高效，适合较大数值的计算。
基本上就这些常见技巧。基础递归用于理解原理，记忆化解决效率问题，尾递归风格提升运行表现。实际使用中，若追求极致性能，可改用迭代，但递归写法更贴近数学定义，便于理解和教学。
