C++ 递归

递归指函数在执行过程中直接或间接调用自身。每次调用占用新的栈帧保存局部变量与返回地址；若缺少终止条件或递归过深，可能导致栈溢出。本节在掌握函数与条件分支后，给出典型递归模式及与迭代的对比。

到达终止条件则直接返回；否则调用自身处理更小的问题，再汇合结束。

递归的两要素

• 终止条件（基线情况）：不再递归，直接返回已知结果。
• 递归分支：将问题化为规模更小（或更简单）的同类子问题，并调用自身。

缺少终止条件或递归分支未使参数向终止条件靠近，将导致无限递归。

阶乘示例

#include <iostream>

unsigned long fact(unsigned n) {
    if (n <= 1) {
        return 1;
    }
    return n * fact(n - 1);
}

int main() {
    std::cout << fact(5) << std::endl;
    return 0;
}

调用 fact(5) 展开为 5 * fact(4)，直至 fact(1) 返回 1。返回值沿调用链回传并相乘。参数 n 在每次递归中减 1，保证最终到达 n <= 1。

先一层层往下拆，每一层都停在乘法左边，等右边的 fact(n - 1) 返回：

fact(5) → 等 fact(4)
fact(4) → 等 fact(3)
fact(3) → 等 fact(2)
fact(2) → 等 fact(1)
fact(1) → 到达 n <= 1，返回 1

再从最底层往回乘：

fact(1) = 1
fact(2) = 2 × 1 = 2
fact(3) = 3 × 2 = 6
fact(4) = 4 × 6 = 24
fact(5) = 5 × 24 = 120

因此 main 里打印 120。中间同时存在着 5 层调用，各有自己的 n；最底层返回后，外层才能算完自己的乘法。

斐波那契（教学版）

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

这段写法与斐波那契数列的数学定义一致，因此容易看懂；可是 fib(n - 1) 与 fib(n - 2) 会各自再往下拆，同一组较小的 n 会被反复算很多遍，所以 n 稍大就会明显变慢。实际项目里更常见的是改成循环，或把已经算过的结果存起来再用（记忆化），也可以写成动态规划。即便如此，递归形式仍适合用来看清问题如何拆开、调用如何叠在栈上。

递归与迭代对比

何时选用递归

• 结构递归：树、链表等定义本身具有递归性质时，代码与定义一致（完整指针操作见指针）。
• 分治：将问题拆为规模更小的同类子问题，合并代价可接受。
• 深度限制：深度与输入规模同阶或更大时，须评估栈限制；必要时改迭代或尾递归优化（编译器未必保证）。

相互递归

函数 A 调用 B，B 再调用 A，亦属递归。声明顺序上可能需要前向声明，与多函数协作相同：

bool is_even(int n);  // 前向声明

bool is_odd(int n) {
    return n == 0 ? false : is_even(n - 1);
}

bool is_even(int n) {
    return n == 0 ? true : is_odd(n - 1);
}

教学示例仅说明机制；实际判断奇偶应直接取模或位运算。

本节说明了递归的终止条件、阶乘与斐波那契示例及与迭代的取舍。下一节介绍头文件与多文件：声明与定义的分离及 include guard。