B 班 第 7 课：递归

适用对象： 完成第 6 课（函数）的同学 使用方式： 自学讲义，Dev-C++ 5.11。边读边敲，做完练习再进入下一课 学完本课，你应该能：

1. 说出递归三要素，并用它们检查自己写的递归对不对
2. 看懂一段递归的执行顺序，说清楚"递下去"和"归回来"分别在干什么
3. 独立写出阶乘、斐波那契、汉诺塔这三个经典递归
4. 判断一道题该用递归还是该用循环

这一课的好消息： 递归在 Python 和 C++ 里写法几乎一模一样——差别还是上节课那四处。真正难的不是语法，是"想明白"，两种语言在这一点上一样难。

0. 热身：函数回顾（10 分钟）

先把上节课的手感捡回来。这个程序用一个函数判断某个数是不是质数：

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    if (isPrime(n)) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

输入 17，输出：yes；输入 18，输出：no

返回值类型写在函数名前面、函数定义在 main 上面、return 一执行函数就立刻结束——这三样今天全程都会用到。

1. 递归：函数调用自己（20 分钟）

上节课我们让 main 调用 isPrime。今天问一个奇怪的问题：函数能不能调用它自己？

能。这就叫递归。

Python 你这样写：

def fac(n):
    if n == 1:
        return 1
    return n * fac(n - 1)

print(fac(5))

C++ 改成这样：

#include <bits/stdc++.h>
using namespace std;

int fac(int n) {
    if (n == 1) return 1;
    return n * fac(n - 1);
}

int main() {
    cout << fac(5) << endl;
    return 0;
}

输出：120

只有这几个不同：

• 没有 def，直接写返回值类型 int
• 参数要写类型：int n
• 函数体靠 { } 不靠缩进
• 函数必须定义在 main 前面

……全是上节课那四处。递归本身，两边一个字都没变。 所以你 Python 里怎么想的，C++ 里就怎么想。

📝 函数在自己的函数体里调用自己，这在 C++ 里是完全合法的，不需要提前声明什么，就那么直接写。

它凭什么能算出来

fac(5) 的执行过程：

fac(5) 要算 5 * fac(4)  ← 卡在这里，等 fac(4)
  fac(4) 要算 4 * fac(3)  ← 卡在这里，等 fac(3)
    fac(3) 要算 3 * fac(2)  ← 卡在这里，等 fac(2)
      fac(2) 要算 2 * fac(1)  ← 卡在这里，等 fac(1)
        fac(1) 碰到 n == 1，直接返回 1     ← 到底了！
      fac(2) 拿到 1，算出 2 * 1 = 2，返回 2
    fac(3) 拿到 2，算出 3 * 2 = 6，返回 6
  fac(4) 拿到 6，算出 4 * 6 = 24，返回 24
fac(5) 拿到 24，算出 5 * 24 = 120，返回 120

先一路"递"下去，碰到底了，再一路"归"回来。 递 + 归 = 递归。

⚠️ 每一层的 n 都是独立的。 fac(5) 里的 n 是 5，fac(4) 里的 n 是 4，互不干扰——这正是上节课讲的"参数是复印件"，每次调用都会有一份自己的复印件。

递归三要素

写递归之前，先在草稿纸上回答这三个问题。三条缺一条，程序就崩。

⚠️ 三条里最容易漏的是 ①。 没有边界条件的递归会一直往下递，直到把系统给程序的那块内存（叫"栈"）撑爆——运行时直接崩溃，而编译器一个字都不会提醒你。

Python 里漏了边界，你会看到 RecursionError: maximum recursion depth exceeded，还算客气；C++ 这边连提示都没有，程序就那么闷声消失了，这是两边最大的体验差异。

动手检查点 1（5 分钟）

新建 check1.cpp，照着上面写出 fac，输出 fac(1) 到 fac(6) 六个结果。

答案应该是 1 2 6 24 120 720。

2. 递下去和归回来：看清执行顺序（20 分钟，本课重点）

阶乘那个例子里，"递"和"归"混在一个 return 里，看不太清。换个例子，把两者彻底分开。

任务：把一个整数的每一位拆出来输出。

先想清楚递推关系：1234 的个位是 1234 % 10，剩下的部分是 1234 / 10 = 123——这是第 3 课学的整除和取余，直接搬过来。

写法一：先输出，再递下去

#include <bits/stdc++.h>
using namespace std;

void printDigits(int n) {
    if (n == 0) return;              // ① 边界：拆没了就停
    cout << n % 10 << " ";           // 先输出个位
    printDigits(n / 10);             // 再去处理剩下的
}

int main() {
    printDigits(1234);
    cout << endl;
    return 0;
}

输出：4 3 2 1

写法二：先递下去，再输出——只是把两行调了个个儿：

#include <bits/stdc++.h>
using namespace std;

void printDigits(int n) {
    if (n == 0) return;
    printDigits(n / 10);             // 先去处理剩下的
    cout << n % 10 << " ";           // 等它全弄完了，再输出个位
}

int main() {
    printDigits(1234);
    cout << endl;
    return 0;
}

输出：1 2 3 4

两行代码换个位置，输出就反过来了。 这是本课最值得盯着看的一个现象。

原因在这里：

写法一（输出写在递归调用前面）：       写法二（输出写在递归调用后面）：

printDigits(1234) 输出 4               printDigits(1234) ──┐
  printDigits(123) 输出 3                printDigits(123) ─┐│
    printDigits(12) 输出 2                 printDigits(12) ┐││
      printDigits(1) 输出 1                  printDigits(1)┐│││
        printDigits(0) 停                      printDigits(0) 停
                                             ↓ 归回来的路上才输出
"递下去"的路上就把话说完了          输出 1 → 输出 2 → 输出 3 → 输出 4

📝 递归调用前面的代码，在"递下去"的路上执行，顺序是从大到小；递归调用后面的代码，在"归回来"的路上执行，顺序是从小到大。

⚠️ 这一条是递归最容易看错的地方。 以后写"十进制转二进制""树的遍历"这类题，输出正着还是反着，全看这一行摆在递归调用的哪一边。

📝 void 函数里的 return; 后面不跟东西（上节课的卫语句），它的作用只是"到此为止，别往下走了"。在递归里，这就是边界条件的标准写法。

动手检查点 2（5 分钟）

新建 check2.cpp，把写法二里的 printDigits(n / 10); 和 cout 那一行交换回来，用 9876 测一遍两种写法。

一个应该输出 6 7 8 9，另一个应该输出 9 8 7 6。亲手换一次，比读十遍讲解管用。

3. 三个经典递归（20 分钟）

例一：斐波那契数列

数列长这样：1, 1, 2, 3, 5, 8, 13, 21, ...，从第 3 项起，每一项都是前两项之和。

三要素：

• ① 边界条件：f(1) = 1，f(2) = 1（这里要两个边界，因为递推关系一次要用到前两项）
• ② 递推关系：f(n) = f(n-1) + f(n-2)
• ③ 规模递减：n-1 和 n-2 都在变小 ✓

Python 你这样写：

def f(n):
    if n <= 2:
        return 1
    return f(n - 1) + f(n - 2)

print(f(10))

C++ 改成这样：

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    cout << f(10) << endl;
    return 0;
}

输出：55

⚠️ 边界写成 if (n == 1) return 1; 单独一条是不够的。 只挡住 n == 1，f(2) 就会去算 f(1) + f(0)，f(0) 又去算 f(-1) + f(-2)……参数越来越小，永远碰不到 n == 1 这个边界，直接崩溃。写成 n <= 2 才是把门关严了。

📝 边界条件要挡住所有"再往下就不对劲"的情况，不是只挡住那一个正好的值。 拿不准就用 <= 而不是 ==。

例二：数组求和

上节课我们用循环求过数组的和。递归也能做：

#include <bits/stdc++.h>
using namespace std;

int a[105];

int sum(int n) {                     // 求 a[0] 到 a[n-1] 的和
    if (n == 0) return 0;            // ① 一个数都没有，和是 0
    return sum(n - 1) + a[n - 1];    // ② 前 n-1 个的和，再加上最后一个
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << sum(n) << endl;
    return 0;
}

输入 5 和 3 1 4 1 5，输出：14

📝 注意数组 a 是全局变量，没有当参数传。 递归函数的参数只放"每层会变的东西"（这里是 n），不变的东西（整个数组）放全局，能省很多事——这是上节课全局变量那一节的实际用途。

例三：汉诺塔

三根柱子 A、B、C，A 上面套着 n 个盘子，大的在下小的在上。要把它们全搬到 C 上，规则是一次只能搬一个，而且任何时候大盘子都不能压在小盘子上面。

n 很大的时候，人脑根本想不清具体步骤。但递归只需要想一层：

• ① 边界条件：只有 1 个盘子，直接从 A 搬到 C，完事
• ② 递推关系：先把上面 n-1 个从 A 挪到 B（借助 C），再把最大的那个从 A 搬到 C，最后把 n-1 个从 B 挪到 C（借助 A）
• ③ 规模递减：每次都变成 n-1 ✓

第 ② 步里的"把 n-1 个挪过去"怎么做？不用管，交给递归——这正是递归最爽的地方。

#include <bits/stdc++.h>
using namespace std;

// 把 n 个盘子从 from 柱搬到 to 柱，via 柱当中转站
void hanoi(int n, char from, char via, char to) {
    if (n == 1) {
        cout << from << " -> " << to << endl;
        return;
    }
    hanoi(n - 1, from, to, via);              // 上面 n-1 个：from → via
    cout << from << " -> " << to << endl;     // 最大的那个：from → to
    hanoi(n - 1, via, from, to);              // 那 n-1 个：via → to
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

输入 3，输出：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

7 步，一步不多一步不少。

⚠️ 两次递归调用的三个柱子参数顺序是不一样的，别照抄第一行。第一次是 from, to, via（C 当中转），第二次是 via, from, to（A 当中转）。写的时候对着注释一个一个核。

📝 递归的思维方式：只想一层，剩下的交给它自己。 你不需要在脑子里把 7 步全推一遍——你只需要保证"这一层做的事是对的"，并且"规模在变小"，剩下的它会自己完成。这是本课最重要的一句话。

4. 递归 vs 循环：什么时候用哪个（10 分钟）

第 3 节的例一、例二，其实用循环都能写，而且更快。那递归是不是多此一举？

先看一个残酷的事实。给斐波那契加个计数器，数数每个 f(i) 到底被算了多少遍：

#include <bits/stdc++.h>
using namespace std;

int cnt[25];

int f(int n) {
    cnt[n]++;                        // 每被调用一次就记一笔
    if (n <= 2) return 1;
    return f(n - 1) + f(n - 2);
}

int main() {
    cout << "f(10) = " << f(10) << endl;
    for (int i = 1; i <= 10; i++) {
        cout << "f(" << i << ") 被算了 " << cnt[i] << " 遍" << endl;
    }
    return 0;
}

输出：

f(10) = 55
f(1) 被算了 21 遍
f(2) 被算了 34 遍
f(3) 被算了 21 遍
f(4) 被算了 13 遍
f(5) 被算了 8 遍
f(6) 被算了 5 遍
f(7) 被算了 3 遍
f(8) 被算了 2 遍
f(9) 被算了 1 遍
f(10) 被算了 1 遍

算一个 f(10)，一共调用了 109 次函数。 f(2) 一个人就被重复算了 34 遍——同一个答案，反反复复算，全是白工。

n 再大一点会更夸张：f(45) 用这个写法能跑到你怀疑电脑坏了。同样的题，用循环写只要 45 步。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a = 1, b = 1;
    int n;
    cin >> n;
    for (int i = 3; i <= n; i++) {
        long long c = a + b;         // 新的一项 = 前两项之和
        a = b;
        b = c;                       // 整体往后挪一格
    }
    cout << (n <= 2 ? 1 : b) << endl;
    return 0;
}

输入 10，输出：55；输入 45，瞬间出结果。

📝 "把算过的答案存起来别重复算"这个办法叫记忆化，它是动态规划的入门，以后学。 今天先知道有这么个坑就够了。

那什么时候该用递归？

📝 判断标准：如果你能一眼看出"第 i 步该干什么"，用循环；如果只能说清"这一层该干什么，剩下的和它长得一样"，用递归。

5. 读错误：3 个递归专属的坑（10 分钟）

坑 1：忘了边界条件（本课头号错误）

int fac(int n) {
    return n * fac(n - 1);        ← 没有 if (n == 1) return 1;
}

编译完全通过，一个警告都没有。运行的时候程序直接消失，或者弹一个窗口说程序停止工作。

因为每调用一层，系统都要留一小块内存记住"回来之后接着干什么"，这块地方叫栈。递归不停下来，栈就被撑爆了，这叫栈溢出。

📝 写 void dfs( 或任何递归函数的第一行时，就顺手先把 if (...) return ...; 写好，再写下面的逻辑。 养成这个手部动作，能省掉一大半调试时间。

坑 2：参数没有朝边界靠近

int fac(int n) {
    if (n == 1) return 1;
    return n * fac(n);            ← 传的是 n，不是 n - 1
}

三要素的第 ③ 条没满足。fac(5) 调用 fac(5) 调用 fac(5)……永远到不了 n == 1，照样栈溢出。

📝 检查递归的手法：把你写的递归调用那一行盯住，问一句"这个参数比外面那个小吗？" 答不上来就是有问题。

坑 3：int 装不下了

int fac(int n) {
    if (n == 1) return 1;
    return n * fac(n - 1);
}
int main() { cout << fac(13) << endl; }

输出 1932053504。而 13 的阶乘真实值是 6227020800，差了一大截。

int 最大只能装到 2147483647，12! 是 479001600 还塞得下，13! 就装不下了——多出来的部分被悄悄丢掉，得到一个看似正常实则完全错误的数字。上节课练习 5 你已经见过一次了。

📝 阶乘、斐波那契、连乘这类题，返回值一律先写 long long。 long long 能装到 9223372036854775807，20! 正好塞得下。输出时不用改任何写法，cout 照常。

⚠️ 这三个坑有个共同点：编译器全都不报错。 递归的错误几乎都是运行时才暴露的，所以写完一定要拿小数据亲手跑一遍。

6. 本课练习（8 题，35 分钟起步，做不完当课后作业）

⭐ 基础题 1：递归求 1 加到 n（文件名 t1.cpp）

写一个函数 int sum(int n)，用递归求 1 + 2 + … + n。主程序读入 n 并输出结果。

输入样例：
100

输出样例：
5050

#include <bits/stdc++.h>
using namespace std;

int sum(int n) {
    if (n == 1) return 1;            // ① 边界
    return n + sum(n - 1);           // ② 递推：前 n-1 个的和，再加上 n
}

int main() {
    int n;
    cin >> n;
    cout << sum(n) << endl;
    return 0;
}

⭐ 基础题 2：阶乘（文件名 t2.cpp）

读入 n（1 ≤ n ≤ 20），用递归求 n 的阶乘。

⚠️ 想清楚返回值该用什么类型再动手。

输入样例：
20

输出样例：
2432902008176640000

#include <bits/stdc++.h>
using namespace std;

long long fac(int n) {               // ← 返回值必须是 long long
    if (n == 1) return 1;
    return n * fac(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << fac(n) << endl;
    return 0;
}

⭐ 基础题 3：正序输出每一位（文件名 t3.cpp）

读入一个正整数，用递归把它的每一位从高位到低位输出，中间用空格隔开。

输入样例：
1234

输出样例：
1 2 3 4 

#include <bits/stdc++.h>
using namespace std;

void printDigits(int n) {
    if (n == 0) return;
    printDigits(n / 10);             // 先递下去
    cout << n % 10 << " ";           // 归回来的路上才输出
}

int main() {
    int n;
    cin >> n;
    printDigits(n);
    cout << endl;
    return 0;
}

⭐⭐ 实战题 4：斐波那契（文件名 t4.cpp）

读入 n（1 ≤ n ≤ 40），输出斐波那契数列的第 n 项。数列是 1, 1, 2, 3, 5, 8, …

⚠️ n 可以到 40，用裸递归会慢到你以为死机了。想想第 4 节。

输入样例：
10

输出样例：
55

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << (n <= 2 ? 1 : b) << endl;
    return 0;
}

⭐⭐ 实战题 5：递归找数组最大值（文件名 t5.cpp）

把第 6 课用循环写的"打擂台找最大值"改写成递归。写一个函数 int maxOf(int n)，返回全局数组 a[0] 到 a[n-1] 里的最大值。

输入样例：
5
35 82 47 90 16

输出样例：
90

#include <bits/stdc++.h>
using namespace std;

int a[105];

int maxOf(int n) {
    if (n == 1) return a[0];             // ① 只有一个数，它就是最大的
    int rest = maxOf(n - 1);             // ② 先问出前 n-1 个里最大的
    return rest > a[n - 1] ? rest : a[n - 1];   // 再和最后一个比一下
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << maxOf(n) << endl;
    return 0;
}

⭐⭐ 实战题 6：汉诺塔（文件名 t6.cpp）

读入盘子数 n（1 ≤ n ≤ 10），输出把 n 个盘子从 A 柱搬到 C 柱的每一步，以及总共几步。

输入样例：
3

输出样例：
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
共 7 步

#include <bits/stdc++.h>
using namespace std;

int step = 0;                        // 全局计数器

void hanoi(int n, char from, char via, char to) {
    if (n == 1) {
        cout << from << " -> " << to << endl;
        step++;
        return;
    }
    hanoi(n - 1, from, to, via);
    cout << from << " -> " << to << endl;
    step++;
    hanoi(n - 1, via, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    cout << "共 " << step << " 步" << endl;
    return 0;
}

⭐⭐⭐ 冲刺题 7：递归判断回文（文件名 t7.cpp）

读入一个字符串（不含空格），判断它是不是回文（正着读和倒着读一样，比如 level、abcba）。要求用递归判断，是输出 yes，不是输出 no。

输入样例：
level

输出样例：
yes

#include <bits/stdc++.h>
using namespace std;

string s;

bool check(int l, int r) {           // 判断 s[l] 到 s[r] 这一段是不是回文
    if (l >= r) return true;         // ① 只剩 0 个或 1 个字符，一定是回文
    if (s[l] != s[r]) return false;  // 两头对不上，直接判死
    return check(l + 1, r - 1);      // ② 两头都对，把两头砍掉继续问
}

int main() {
    cin >> s;
    if (check(0, s.length() - 1)) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

⭐⭐⭐ 冲刺题 8：十进制转二进制（文件名 t8.cpp）

读入一个正整数 n（1 ≤ n ≤ 1000），用递归输出它的二进制表示。

思路提示： n 除以 2 的余数就是二进制的最后一位，n / 2 是剩下的部分。但余数是倒着出来的，想想第 2 节。

输入样例：
13

输出样例：
1101

#include <bits/stdc++.h>
using namespace std;

void toBinary(int n) {
    if (n == 0) return;
    toBinary(n / 2);                 // 先递下去
    cout << n % 2;                   // 归回来的路上才输出
}

int main() {
    int n;
    cin >> n;
    toBinary(n);
    cout << endl;
    return 0;
}

7. 学有余力：辗转相除法求最大公约数（加餐，可跳过）

求两个数的最大公约数（GCD），有个两千年前就有的办法叫辗转相除法：

gcd(a, b) 等于 gcd(b, a % b)，直到 b 变成 0，这时候 a 就是答案。

写成递归只有三行：

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

输入 24 18，输出：6

跟一遍：gcd(24, 18) → gcd(18, 6) → gcd(6, 0) → 返回 6。

三要素全齐：① 边界 b == 0；② 递推 gcd(a,b) = gcd(b, a%b)；③ 每次的 b 都是上一次的余数，余数一定比除数小，所以一路减到 0。

📝 有了 GCD，最小公倍数（LCM）也就有了： a * b / gcd(a, b)。注意先除后乘更安全（a / gcd(a,b) * b），能避开中间结果溢出。

这三行是全世界最著名的递归之一，值得背下来——以后做分数化简、周期问题都会用到。

本课要点速查

Python ↔︎ C++ 递归对照：

递归三要素：

递下去 vs 归回来：

void f(int n) {
    if (边界) return;
    A;            ← 写在这里：在"递下去"的路上执行，顺序从大到小
    f(更小的 n);
    B;            ← 写在这里：在"归回来"的路上执行，顺序从小到大
}

递归还是循环：

易错点：

以后学： 记忆化（把算过的答案存起来，斐波那契那个坑的正解）与动态规划、二维数组、结构体、指针、vector、深度优先搜索 DFS（递归在搜索题里的正式用法）。今天的三要素到那时候一个字都不用改。

结束前的自我检查

1. 不看讲义，说出递归三要素，并用它们检查一遍你写的 t2.cpp
2. 说清楚为什么斐波那契的边界要写 n <= 2 而不是 n == 1
3. 用一句话解释：cout 写在递归调用前面和后面，输出顺序有什么区别
4. 练习 1~6 全部通过；⭐⭐⭐ 第 7、8 题至少独立做出一道
5. 把 t2.cpp 的 long long 改回 int，输入 20 跑一遍，亲眼看看溢出成什么样；再把边界那一行删掉跑一遍，看看程序是怎么"闷声消失"的