波仔
🔷 第六章 函数
📄 一句话概括

递归 = 函数调用它自己：把大问题拆成"同类型的小问题"，一层层递下去直到能直接回答的最小情形（出口），再一层层把答案归回来。两个必备要素：出口（什么时候停）+ 向出口靠近（每次拆得更小）——缺任何一个都会栈溢出。

📝 本节和前面几节的关系

6.3.2 的嵌套调用是"A 调 B"，递归是"A 调 A"——最特殊的一种嵌套调用。它复用 6.3 那套调用栈，所以必须警惕"层数太深、栈装不下"。本节还会把第五章的循环拉过来对照：同一个问题，循环和递归都能解，选谁看问题形状。

一、递归的两要素（缺一不可）

int fact(int n) {
    if (n <= 1) return 1;        // ① 出口：最小的情形直接给答案
    return n * fact(n - 1);      // ② 向出口靠近：每次的 n 都小 1
}
要素 作用 缺了会怎样
出口（基准情形） 什么时候停止拆 一直拆下去 → 栈溢出崩溃
向出口靠近 每次拆都更小 参数不变 → 死循环，同样崩

记忆句：递归像下楼梯——必须每一级都往下走，还得有个最低层。

二、递归的两段动作："递"与"归"

以 fact(5) 为例：

递（往下钻）：

fact(5) = 5 × fact(4)
              fact(4) = 4 × fact(3)
                            fact(3) = 3 × fact(2)
                                          fact(2) = 2 × fact(1)
                                                        fact(1) = 1   ← 出口

归（往上拼）：

1  →  2×1=2  →  3×2=6  →  4×6=24  →  5×24=120

"递"是去程、"归"是回程——递归的名字就来自这两段。

三、实例 05：求 n 的阶乘（循环版 vs 递归版）

教材的实例是用循环求阶乘，这里把两种写法并排看：

// 版本一：循环（第五章的做法）
int factLoop(int n) {
    int r = 1;
    for (int i = 1; i <= n; i++) r *= i;
    return r;
}

// 版本二：递归（本节的做法）
int factRec(int n) {
    if (n <= 1) return 1;
    return n * factRec(n - 1);
}

完整程序：

#include <iostream>
using namespace std;

int factLoop(int n) {
    int r = 1;
    for (int i = 1; i <= n; i++) r *= i;
    return r;
}

int factRec(int n) {
    if (n <= 1) return 1;            // 出口
    return n * factRec(n - 1);       // 向出口靠近
}

int main() {
    for (int n = 1; n <= 6; n++) {
        cout << n << "! = " << factLoop(n)
             << " , 递归版 " << factRec(n) << endl;
    }
    return 0;
}

看到什么算成功：

1! = 1 , 递归版 1
2! = 2 , 递归版 2
3! = 6 , 递归版 6
4! = 24 , 递归版 24
5! = 120 , 递归版 120
6! = 720 , 递归版 720

两列完全一致——递归不是玄学，只是另一种写法。

⚠️ 一个真实的坑：int 装不下 13! 以上（13! ≈ 62 亿 > int 上限约 21 亿），会溢出回绕成负数（2.3.3 的老坑）。试试输出 factRec(15) 看结果有多离谱——这是"类型范围"知识的实战复习。

30 秒实验：把出口条件从 if (n <= 1) 改成 if (n == 1)，然后调 factRec(0)——它会一路接到 factRec(-1)、factRec(-2)……栈溢出崩溃。体会"出口必须覆盖所有该停的情形"这句话。

四、什么时候用递归（判断标准）

适合 不适合
问题本身是"同类更小问题"的重复：阶乘、斐波那契、汉诺塔、树的遍历、二分查找 简单的数字累加、遍历数组——循环更直接更快
代码能短很多、逻辑一眼看懂 递归深度很大（几千层）——栈装不下

一句话：递归负责"把问题说清楚"，循环负责"把活干快"。能用循环轻松表达就别硬凹递归；但遇到"天然分层"的问题（树、目录、括号匹配），递归往往是最省心的表达。

五、常见误区

  1. "递归比循环高级"——不是。每次递归都要记位置、开变量（6.3 的栈机制），通常比循环慢。选谁看问题形状。
  2. "有出口就一定安全"——还得看深度。factRec(100000) 是有出口的，但十万层调用直接撑爆栈。
  3. "递归调用不用写 return"——这是递归第一大坑。写成 factRec(n - 1);（漏 return）时能编过、也确实在递归，但每层都把算出来的值扔了，最后交回垃圾值。写完照着模板逐字比对 return。
  4. "递归里同名变量会互相干扰"——不会。每次调用都新开一套形参和局部变量（6.2.2 的复制 + 6.3 的栈），各层的 n 各管各的。
自测三问（点开对答案） 1. 递归的两个必备要素是什么？——出口（停止条件）和向出口靠近（每次问题变小）。 2. "递"和"归"分别指什么？——递是往下拆问题，归是把答案一层层拼回来。 3. 递归里漏写 `return` 会怎样？——能编过、也在递归，但每层的返回值被丢弃，最终得到垃圾值。

相关笔记