Lecture 5: 递归：原理、策略与递归式思维（Recursion: Principles & Strategies）（对应课程真实讲座 L08–L10）

目录 · ← l4 · l6 →

Lecture 5: 递归：原理、策略与递归式思维（Recursion: Principles & Strategies）（对应课程真实讲座 L08–L10）

概述

本讲正式引入”递归（recursion）”：让函数调用自己，把一个大问题不断拆成同构（形状相同、规模更小）的子问题，直到某个最小问题能直接给出答案。我们会从阶乘、回文这类”热身”例子中吃透递归三要素与调用栈机制，再实现递归二分查找、字符串逆序打印和全排列枚举——这些技巧是后续回溯、分治（归并/快排）与树遍历的共同地基。 （对应官方 2026 夏季 CS106B：L08 Monday, July 6 “Introduction to Recursion”；L09 Tuesday, July 7 “More Recursion”；L10 Wednesday, July 8 “Recursive Problem Solving”。官方在第 8 讲开篇就让大家 DON’T PANIC——递归第一次出现在代码里觉得”玄、晕、难”完全正常，多练习就会变成第二天性。）

核心概念与算法原理

1. 什么是递归：函数调用自己

• 问题定义：要解决问题 P(输入 x)，先把 x 拆成一个或多个”更小的 x’“，然后调用正在写的这个函数自己去解决 P(x’)，最后把子问题的答案拼成 P(x) 的答案。
• 直观解释：俄罗斯套娃——打开最大的娃娃，里面是一个小一号的娃娃，再打开又是一个更小的；大自然里 Koch 雪花、罗马花椰菜都呈现这种”整体里嵌套同形局部”的自相似（self-similar）结构。
• 官方在第 8 讲给出递归函数的两大关键组件，也就是常说的三要素：
  1. 基准情形（base case）：对某些”显然能答”的规范输入直接返回结果，不再调用自己——这是递归的终止条件；
  2. 递归步骤（recursive case）：把当前输入分解成子问题，其中至少一个交给函数自身处理；
  3. 向基准靠拢（progress toward base case）：每次递归调用传入的输入必须比当前更”小”，保证迟早撞上基准情形——而不是朝反方向无限增长。

2. 调用栈：先”递”下去，再”归”回来 程序运行时，每调用一次函数，系统就在内存的”程序栈（call stack）”上压入一个栈帧（stack frame），记录参数、局部变量和返回地址；函数返回时该帧弹出。递归 = 不断压栈（”递”的过程），撞到基准后逐层弹出（”归”的过程），每层带着返回值回到上一层继续未完成的计算。以阶乘为例（本讲第一个正式程序），factorial(5) 的栈是这样长高又变矮的：

factorial(5) 的调用栈（框越往上越"新"；栈顶是最深的那一层调用）

“递”的途中：一帧一帧压栈
┌────────────────────────────────┐
│ factorial(0)   基准情形 return 1│ ← 栈顶（最深）
├────────────────────────────────┤
│ factorial(1)   等待 1 × ____    │
├────────────────────────────────┤
│ factorial(2)   等待 2 × ____    │
├────────────────────────────────┤
│ factorial(3)   等待 3 × ____    │
├────────────────────────────────┤
│ factorial(4)   等待 4 × ____    │
├────────────────────────────────┤
│ factorial(5)   等待 5 × ____    │
├────────────────────────────────┤
│ main()                         │
└────────────────────────────────┘

“归”的途中：帧从栈顶依次弹出，返回值逐层回传、就地完成乘法：
factorial(1) = 1 × 1   = 1
factorial(2) = 2 × 1   = 2
factorial(3) = 3 × 2   = 6
factorial(4) = 4 × 6   = 24
factorial(5) = 5 × 24  = 120   ← 最终答案交回给 main()

3. 无限递归与栈溢出（stack overflow） 如果函数没有基准情形、或递归调用不向基准靠拢，栈帧会无穷无尽地堆积，最终占满栈空间导致程序崩溃（官方在第 8 讲用 foo(){ foo(); } 演示，崩溃前能压入约二十六万个帧）。规避方法只有一个：动笔写递归体之前，先问自己”最小输入是什么？答案是什么？参数怎么变小？”

4. 递归 vs 迭代 官方在第 8 讲直言：今天大部分例子用 for 循环也能写，我们偏要用递归，是为了用温和的题目建立递归直觉。两者的取舍大致是：

5. 信任飞跃（leap of faith） 写递归最常见的心理障碍是想把每一层调用都追踪一遍。官方反复鼓励的姿势恰恰相反：假设”对更小输入的递归调用已经正确返回了”，你只需负责当前这一层如何利用子结果、以及基准情形是否正确。好比接力赛中你相信前一棒会把棒交到你手里，你只操心自己这一段怎么跑。

6. 包装函数（wrapper function）与函数重载（overloading） 递归函数往往需要额外参数（如二分查找的 lo、hi），但调用者不想关心这些。于是写一个”门面”包装函数：只接收用户想传的参数，内部负责初始化并调用真正的递归函数；若两函数同名（仅参数不同），就叫函数重载，C++ 会根据实参个数与类型自动选择调用哪一个——这比 xxxHelper 式的命名更清爽（官方在第 9 讲的二分查找里就用了两个同名 binarySearch）。

7. 语句顺序决定输出顺序：打印 vs 递归 递归调用前后各放一句代码，执行时机完全不同：调用之前的语句在”递”的途中执行（自顶向下）；调用之后的语句要等子调用全部返回才执行，即”归”的途中执行（自底向上）。正序打印字符串，就是先打印再递归；逆序打印只需把两句对调——栈天然替我们把顺序反转了：

#include <iostream>
#include <string>
using namespace std;

// 先打印、后递归：顺着"递"的路径输出 → 正序
void printForward(const string& s, int k) {
    if (k == (int)s.length()) { cout << endl; return; }
    cout << s[k];
    printForward(s, k + 1);
}
// 先递归、后打印：顺着"归"的路径输出 → 逆序
void printBackward(const string& s, int k) {
    if (k == (int)s.length()) { return; }
    printBackward(s, k + 1);
    cout << s[k];
}

注意逆序版里换行若放在基准情形，会打印在整串之前（基准最先执行），正确做法是把换行交给包装函数收尾——这就是”包装函数负责 setup/tear-down”的典型用途（官方第 8 讲的教训）。

8. 从线性查找到递归二分查找（binary search）

• 线性查找（linear search）：从下标 0 逐个比到末尾，找到即停。它不要求数据有序，但最坏要扫 n 个元素。
• 二分查找：前提是容器已按非降序排好。每次取当前搜索区间 [lo, hi] 的中点 mid 与 key 比较：key 小则 key 只可能落在左半 [lo, mid-1]，key 大则只可能在右半 [mid+1, hi]——无论哪种，都一次性丢掉一半搜索空间。官方在第 9 讲强调：每步 O(1) 的比较把空间减半，正是第 7 讲讲的”对数运行时”：1 亿（约 2³⁰）个元素也只需约 30 次比较。
• 中点公式的溢出陷阱（官方第 9 讲补充）：int 最大值约 21.47 亿。若 lo、hi 都很大，(lo + hi) / 2 的加法本身可能溢出成负数，得到非法下标导致程序崩溃（如 lo = 1,000,000,001、hi = 2,000,000,001，lo + hi 溢出为 −1,294,967,294）。改用代数等价但永不溢出的 lo + (hi - lo) / 2——中间量最大只到 hi。这个细节常出现在技术面试里。

9. 递归枚举与分形的”预览” 硬币序列（每次抛 H/T，n 次共 2ⁿ 种）、骰子序列（6ⁿ 种）、全排列（n! 种）都属于递归枚举：每层递归在一个”决策点”上尝试所有候选并深入。官方在第 9–10 讲用递归树/Prezi 演示：coinFlip 只是两处递归调用，dice 把两次调用改成 for 循环六次，permutation 则在 for 里逐一挑”下一个字符”。这类问题迭代写非常痛苦、递归写却只有几行，是下一讲”回溯”的直接前奏。分形（Koch 雪花、谢尔宾斯基三角形）则是递归的图形化表达：官方动画特别提醒，代码里四个子段是按深度优先依次画完的（先把最左分支一路画到底再回头），并非并行绘制——递归调用的书写顺序决定图形呈现顺序。

代码示例与实现详解

下面 4 个示例全部只依赖 C++17 标准库、可独立编译运行。

示例 1：递归阶乘——三要素与”递/归”全景

#include <iostream>
using namespace std;

// n! = n × (n-1)!，0! = 1
int factorial(int n) {
    if (n == 0) {          // ① 基准情形：0! 直接给答案
        return 1;
    }
    return n * factorial(n - 1);   // ② 递归步骤 ③ 参数 n-1 朝 0 靠拢
}

int main() {
    for (int n = 0; n <= 10; ++n) {
        cout << n << "! = " << factorial(n) << endl;
    }
    return 0;
}

【代码做什么】：factorial 把 n! 的定义直接翻译成代码：n! = n × (n−1)!。主函数打印 0! 到 10! 验证结果。若把基准情形注释掉或参数写成 n + 1，程序将因栈溢出而崩溃——这是理解递归的第一块试金石。

【实现机制解说】：调用 factorial(5) 时，第 2 节的栈帧图精确描述了全过程：递——五个 factorial 帧层层压栈，每帧都”冻结”在自己那行 return n * factorial(n-1) 上，等待子调用返回值填空；最深处的 factorial(0) 命中基准，直接返回 1，不再压栈；归——从 factorial(1) 起每帧依次弹出并完成自己的乘法，答案如多米诺骨牌般回传。理解”乘法发生在归途、而非递途”是看懂一切递归计算的关键：递途只负责把问题拆到最小，真正的计算在回卷时完成。

示例 2：回文判断——剥皮法递归

#include <iostream>
#include <string>
using namespace std;

// 回文：正着读反着读都一样，如 racecar
bool isPalindrome(const string& s) {
    if (s.length() <= 1) {          // 基准：空串与单字符都是回文
        return true;
    }
    if (s.front() != s.back()) {    // 首尾不等 → 直接判否
        return false;
    }
    // 首尾相同 → 剥掉它们，检查剩下的子串是否回文
    return isPalindrome(s.substr(1, s.length() - 2));
}

int main() {
    for (string t : {"racecar", "kayak", "hello", "a", "", "step on no pets"}) {
        cout << "\"" << t << "\" -> " << (isPalindrome(t) ? "是回文" : "非回文") << endl;
    }
    return 0;
}

【代码做什么】：isPalindrome("racecar") 先比较首 ‘r’ 与尾 ‘r’ 相同，于是递归检查剥皮后的 "aceca"；依次剥到长度 ≤ 1 时返回 true。对 "hello"，首 ‘h’ ≠ 尾 ‘o’，第一层就直接返回 false，不再深入。

【实现机制解说】：这里有两个关键设计。其一，递归调用必须发生在”首尾相等”这一检查之后——官方在第 8 讲的 Common Pitfall #3 指出：若忘了比较首尾就无脑递归，函数会对一切输入返回 true，而且如果你只写了”期望 true”的测试用例，这种坏函数会全部通过，让人毫无察觉。其二，用 substr 切片每次会复制约一半长度的新串（n 层累计约 O(n²) 时间）；若追求效率，可改用”传整个字符串的引用 + 两个下标 lo、hi 向中间靠拢”的写法，每层只做 O(1) 工作（这是官方面试风格的改进题，见思考题）。

示例 3：递归二分查找（含包装重载与防溢出中点）

#include <iostream>
#include <vector>
using namespace std;

// 在有序数组 v 的闭区间 [lo, hi] 内查找 key；找不到返回 -1
int binarySearch(const vector<int>& v, int key, int lo, int hi) {
    if (lo > hi) {                  // 基准：区间为空 → 不存在
        return -1;
    }
    int mid = lo + (hi - lo) / 2;   // 防溢出中点公式（勿写成 (lo+hi)/2）
    if (key < v[mid]) {
        return binarySearch(v, key, lo, mid - 1);   // 只搜左半
    }
    if (key > v[mid]) {
        return binarySearch(v, key, mid + 1, hi);   // 只搜右半
    }
    return mid;                     // key == v[mid]，命中
}

// 包装函数：与上面构成函数重载，调用者只需传数组和 key
int binarySearch(const vector<int>& v, int key) {
    return binarySearch(v, key, 0, (int)v.size() - 1);  // 空数组时 hi=-1 直接命中基准
}

int main() {
    vector<int> v = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    for (int key : {2, 38, 91, 99}) {
        cout << "在有序数组中查找 " << key << " -> 下标 "
             << binarySearch(v, key) << endl;
    }
    return 0;
}

【代码做什么】：每次比较 key 与 v[mid]，据此把搜索区间收缩为左半或右半并递归，直至区间为空（返回 −1）或命中（返回下标）。主函数对四个键演示查找：2 命中下标 0，38 命中下标 6，91 命中下标 9，99 不存在返回 −1。

【实现机制解说】：注意三点。第一，为什么能安全丢掉一半：数组有序，若 key < v[mid]，则 key 不可能出现在 mid 右侧任何位置，右半可以整体放弃——剪枝的正确性完全建立在有序性上，这也是本讲唯一”必须传引用而不传值”也成立的场景（传引用省去每次 O(n) 拷贝，官方在第 9 讲明确传值会变 O(n) 操作）。第二，基准情形 lo > hi：区间收缩到 lo 越过 hi 说明搜索空间已空，这正是”用递归把迭代终止条件表达出来”的典范；空数组经包装函数进入后 hi = −1，同样安全返回。第三，两个同名函数靠参数个数区分（3 参数版 + 2 参数版），这就是函数重载：编译器看到 binarySearch(v, key) 自动选 2 参数版，看到四参调用选 3 参数版。每层递归栈深 O(log n)，约 log₂(10) ≈ 4 层即可查完 10 个元素。

示例 4：递归生成全排列——枚举的雏形

#include <iostream>
#include <string>
using namespace std;

// soFar：已经确定的前缀；rest：还没安放位置的剩余字符
void permute(const string& soFar, const string& rest) {
    if (rest.empty()) {                 // 基准：没有剩余字符 → 得到一个完整排列
        cout << soFar << endl;
        return;
    }
    for (int i = 0; i < (int)rest.length(); ++i) {
        // 把 rest[i] 安到下一个位置，剩余字符 = 去掉 rest[i] 后的串
        string newRest = rest.substr(0, i) + rest.substr(i + 1);
        permute(soFar + rest[i], newRest);   // explore 每一个候选
    }
}

// 包装函数：从空前缀、完整字符串开始
void permute(const string& s) {
    permute("", s);
}

int main() {
    permute("cat");   // 应输出 6 个排列：cat cta act atc tca tac
    return 0;
}

【代码做什么】：permute("", "cat") 在每一层用 for 循环遍历 rest 里的每个字符，将其追加到 soFar 并递归处理剩余字符。当 rest 为空，说明所有字符都已就位，输出一个排列。共输出 3! = 6 行。

【实现机制解说】：这是”决策树”式递归的第一次正式登场：第 1 层有 3 个分支（c/a/t 谁打头），第 2 层每个分支又有 2 个选择，第 3 层 1 个，叶子总数 3×2×1 = 6。因为 soFar、rest 都是按值传递的新拷贝，父调用自身状态从未被改动，返回上一层时”天然撤销”了本层的选择——这个特性在下一讲的回溯里会与”共享状态需要显式撤销”形成鲜明对比。若把本函数改成硬币序列：for 循环换成两次固定递归 coinFlip(soFar+'H', n-1) 与 coinFlip(soFar+'T', n-1)，就得到 2ⁿ 个 H/T 序列（官方第 9 讲的 coinFlip 正是如此）——排列与序列共享同一套”递归枚举”骨架。注意按值传串有拷贝开销（总代价量级 O(n·n!)），面试改进版是传引用 + swap（官方第 10 讲展示过 swap 版排列，需在递归后把字符换回来，即”撤销”）。

复杂度分析

注意：”最好/最坏”永远指输入规模任意大时的差异（官方在第 9 讲强调：不能说”输入只有一个元素时最快”，那样任何函数都成 O(1) 了）；另外回文的 substr 切片版每层复制剩余串，最坏 O(n²)，用下标版可回到 O(n)。

关键要点

• 三要素缺一不可：先有能直接回答的基准情形，再写把输入缩小并调用自己的递归步骤——否则要么栈溢出，要么根本没在递归。
• 用信任飞跃写递归：先假设”更小输入的递归调用是对的”，只检查当前层如何拼装子结果；不要逐层手工追踪。
• 语句的位置决定时机：递归调用之前的代码在”递”时执行，之后的代码在”归”时执行——逆序打印的秘密就在这一行顺序里。
• 用包装函数 + 重载把”用户接口”和”递归细节”分开，让调用者只传最少的参数。
• 递归是”分而治之/自相似”的思维工具：二分把 O(n) 降到 O(log n)，枚举天然指数/阶乘级——能用递归几行说清的问题，往往迭代写起来又长又绕。

常见陷阱与注意事项

1. 忘基准情形或基准漏输入：如 factorial 只判 n == 1，调用 factorial(0) 会无限调用 factorial(-1)… 直至栈溢出（官方 Common Pitfall #2）。规避：把 0、空串这类”边界但合法”的输入都列出来测试；若参数改 unsigned，负数会下溢成巨大正数，同样死循环——类型替代不了基准设计。
2. int 函数漏 return：写下 n * factorial(n - 1); 却没写 return（官方 Common Pitfall #1），结果未定义。规避：编译加 -Wall，并把返回值直接写在 return 表达式里。
3. 回文忘了比较首尾：函数变成恒真，且全 true 的测试还发现不了（官方 Pitfall #3）。规避：测试集必须包含期望 false 的用例。
4. 递归调用不向基准靠拢（如 foo(n+1) 却以 n==0 为基准）。规避：写前先确认每层参数严格”变小”。
5. 改名后忘改函数体内的递归调用（官方 Pitfall #4，常见于复制粘贴）。规避：改名后全文搜索旧函数名。
6. 中点公式写成 (lo+hi)/2 导致大区间溢出崩溃。规避：一律 lo + (hi - lo) / 2。
7. 把换行/收尾语句放进逆序打印的基准情形：换行会出现在整串之前。规避：收尾工作交给包装函数。
8. 每层用 substr 造大拷贝：递归深、串长时浪费严重。规避：传引用 + 下标参数（如 printStringHelper 风格）。

思考题（带答案）

问题 1：把 factorial 的基准情形从 n == 0 改成 n == 1，然后调用 factorial(0) 会发生什么？为什么？ 答案：factorial(0) 不会命中基准（0 ≠ 1），于是调用 factorial(-1)、factorial(-2)……参数不但没向 1 靠拢反而越来越远，栈帧无限堆积，最终栈溢出崩溃。基准情形必须覆盖全部合法输入的边界，且递归方向必须朝向基准。 问题 2：用”信任飞跃”写递归二分查找时，你具体信任了什么？哪些细节可以完全不管？ 答案：信任 binarySearch(v, key, lo, mid-1) 与 binarySearch(v, key, mid+1, hi) 这两个”更小区间”的调用会各自返回正确下标或 −1——不必手工模拟这两次调用内部几十帧的执行。你只需要确保：区间确实在收缩（mid 两侧都严格小于原区间）、基准 lo > hi 正确、以及比较逻辑（小于走左、大于走右、相等命中）在当前层是对的。若这三件事成立，整体必然正确。 问题 3：为什么逆序打印字符串的 endl 不能放在基准情形里？正确的放置位置在哪？ 答案：基准情形是整条递归链最早执行的代码（它在”归”的起点），放在那里会让换行先于任何字符打印出来（输出变成先空一行再是反转串）。正确做法是把换行放在包装函数里：包装函数调用完递归主体后再补 endl，于是换行恰好出现在所有字符之后（官方第 8 讲 printStringReverse 的解法）。