递归函数本质是自己调用自己，必须有明确终止条件；每次调用需逼近边界，否则栈溢出；如斐波那契需设fib(0)、fib(1)为base case，但标准递归时间复杂度达O(2^n)，因重复计算。
递归函数的本质是“自己调用自己”，但必须有明确的终止条件
递归不是神秘操作，它只是把一个大问题拆成结构相同、规模更小的子问题。关键在于：每次调用都得离终止条件更近一步，否则会无限调用导致栈溢出。比如计算 fib(5)，不能直接写 return fib(5);，而要写成 return fib(4) + fib(3);，并规定 fib(0) 和 fib(1) 直接返回值——这就是边界（base case）。
C++斐波那契递归写法：简洁但暗藏性能陷阱
标准递归实现看起来很直观，但时间复杂度是指数级 O(2^n)，因为大量重复计算（如 fib(3) 在 fib(5) 的展开中被算两次）。实际写法如下：
int fib_recursive(int n) {
if (n <= 1) return n; // 终止条件：0→0，1→1
return fib_recursive(n-1) + fib_recursive(n-2);
}
- 输入负数会无限递归，应加校验：
if (n - 即使
n == 40，耗时已明显可感知；n == 50可能卡住几秒——这不是代码错，是算法固有缺陷 - 编译器通常不优化这种多分支递归（不像尾递归），别指望自动转成循环
C++斐波那契迭代写法：用两个变量滚动更新，O(1)空间+O(n)时间
迭代本质是模拟递归的“展开过程”，但不依赖调用栈。核心是只保留最近两个值，逐步推进：
int fib_iterative(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
- 没有函数调用开销，不会栈溢出，
n == 10^6也能秒出结果（只要int不溢出） - 注意整数溢出风险：
int在fib(47)左右就溢出，生产环境建议用long long或std::optional处理失败 - 若需返回整个数列而非单个值，可改为填充
std::vector，但没必要为单次查询预存全部
什么时候该用递归，什么时候必须切迭代？
递归适合结构天然分治的问题（如树遍历、快排分区、表达式解析），而斐波那契只是教学示例——它**没有隐藏状态，无分支回溯，纯线性依赖**，正是迭代最擅长的场景。真实项目中若看到有人对斐波那契用递归，大概率是没想清楚复杂度，或在写玩具代码。
立即学习“C++免费学习笔记（深入）”；
真正要注意的是：别为了“显得高级”硬套递归；也别因怕栈溢出，把所有递归都改成迭代——比如遍历二叉树，强行用栈模拟反而增加理解成本。关键看问题是否具备“子问题独立+可合并”的递归结构。
