Day5 递归递推
2026-07-25 15:18:51
发布于：广东
7阅读
0回复
0点赞
XP02 Day5 递归和递推学习笔记
一、加法原理和乘法原理
1. 为什么先讲这两个原理？
递归和递推经常会遇到：
这个问题可以分成几种情况？
这个问题需要分几步完成？
如果是“分情况”，通常用加法原理。
如果是“分步骤”，通常用乘法原理。
2. 加法原理
加法原理用于：
分类讨论。
它的特点是：
每种情况互相独立；
一个方案只属于其中一种情况；
最后把每种情况的数量相加。
生活例子：
小明早餐可以吃包子，也可以吃面包。
包子有 3 种，面包有 2 种。
小明只选一种早餐。
总选择数是：
3 + 2 = 5
因为“吃包子”和“吃面包”是两类不同情况。
3. 加法原理关键词
看到这些词，可以想到加法原理：
或者
分情况
分类讨论
要么……要么……
4. 乘法原理
乘法原理用于：
分步骤完成。
它的特点是：
一件事要分几步做；
每一步都有若干种选择；
最后把每一步的选择数相乘。
生活例子：
小明要穿一套衣服。
上衣有 3 件，裤子有 2 条。
先选上衣，再选裤子。
总搭配数是：
3 * 2 = 6
因为每一件上衣都可以搭配每一条裤子。
5. 乘法原理关键词
看到这些词，可以想到乘法原理：
先……再……
分步骤
每一步
搭配
组合
6. 加法和乘法的区别
| 原理 | 什么时候用 | 计算方式 |
|---|---|---|
| 加法原理 | 分情况，只选其中一种 | 相加 |
| 乘法原理 | 分步骤，每一步都要做 | 相乘 |
简单记：
分情况用加法。
分步骤用乘法。
二、递归
1. 递归的概念
递归就是：
一个函数在解决问题时，调用自己去解决更小的同类问题。
大纲中的说法可以这样理解：
当我们要解决一个问题时，发现需要先解决它的子问题。
而这个子问题和原问题很像，只是规模更小。
于是我们先解决子问题，再用子问题的答案解决原问题。
2. 生活例子：排队问人数
你站在队伍最前面，想知道队伍一共有多少人。
你可以问后面的人：
你后面有多少人？
后面的人也可以继续问他后面的人。
直到最后一个人，他知道：
我后面没人，所以我这里有 1 个人。
然后答案一层一层传回来。
这就是递归的感觉：
自己解决不了全部，就先让更小的问题给出答案。
3. 递归必须有两个部分
递归函数必须有：
递归出口；
递归关系。
递归出口：
什么时候不再继续调用自己。
递归关系：
当前问题怎样变成更小的问题。
如果没有递归出口，函数会一直调用自己，程序会出错。
4. C++ 中如何实现递归？
C++ 中递归的实现方式是：
函数调用自己。
例如：
void f() {
f();
}
这就是函数调用自己。
但是这个函数没有递归出口，会一直调用下去，是错误写法。
正确递归要有出口。
三、递归例题一：斐波那契数列
1. 题目概念
斐波那契数列是：
1, 1, 2, 3, 5, 8, 13, ...
它的规律是：
第 1 项 = 1
第 2 项 = 1
从第 3 项开始，每一项等于前两项之和
也就是：
f(n) = f(n - 1) + f(n - 2)
2. 为什么适合递归？
要求第 n 项，需要先知道：
第 n - 1 项
第 n - 2 项
这两个问题和原问题一样，都是“求斐波那契数列的某一项”，只是规模更小。
所以可以递归。
3. 递归出口
当：
n == 1 或 n == 2
答案都是 1。
这就是递归出口。
4. 递归代码
#include <bits/stdc++.h>
using namespace std;
long long fib(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
void solve() {
int n;
cin >> n;
cout << fib(n) << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
5. 递归调用过程
求：
fib(5)
会变成：
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
最后遇到：
fib(1) = 1
fib(2) = 1
答案再一层层返回。
6. 重要提醒
普通递归写斐波那契很容易理解，但如果 n 很大，会很慢。
因为很多子问题会被重复计算。
例如：
fib(5) 里面会算 fib(3)
fib(4) 里面也会算 fib(3)
这就引出后面的：
记忆化递归。
四、递归例题二：最大公约数
1. 什么是最大公约数？
最大公约数就是：
两个数共同的约数中最大的那个。
例如：
12 的约数：1, 2, 3, 4, 6, 12
18 的约数：1, 2, 3, 6, 9, 18
共同约数：1, 2, 3, 6
最大公约数是 6
2. 辗转相除法
大纲中给出的公式：
gcd(a, b) = gcd(b, a % b)
意思是：
求 a 和 b 的最大公约数，
可以变成求 b 和 a % b 的最大公约数。
其中 % 是取余。
3. 递归出口
当：
b == 0
答案就是：
a
4. 代码
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
void solve() {
long long a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
5. 过程举例
求：
gcd(18, 12)
过程：
gcd(18, 12)
= gcd(12, 18 % 12)
= gcd(12, 6)
= gcd(6, 12 % 6)
= gcd(6, 0)
= 6
五、扩展：最小公倍数
1. 什么是最小公倍数？
最小公倍数就是：
两个数共同的倍数中最小的那个。
例如：
4 的倍数：4, 8, 12, 16, 20, ...
6 的倍数：6, 12, 18, 24, ...
共同倍数中最小的是 12
所以：
lcm(4, 6) = 12
2. 最大公约数和最小公倍数的关系
公式：
lcm(a, b) = a / gcd(a, b) * b
为什么先除再乘？
为了减少乘法时数字太大导致溢出的可能。
3. 代码
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}
void solve() {
long long a, b;
cin >> a >> b;
cout << lcm(a, b) << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
六、扩展：十进制转 M 进制
1. 问题说明
给一个十进制整数 n，把它转换成 m 进制。
例如：
10 转 2 进制 = 1010
2. 为什么可以递归？
我们可以先得到最后一位：
n % m
剩下的部分是：
n / m
要输出完整的 m 进制，就需要先输出 n / m 的结果，再输出最后一位。
所以递归关系是：
先处理 n / m，再输出 n % m
3. 递归出口
当：
n == 0
就不用继续递归了。
4. 代码
#include <bits/stdc++.h>
using namespace std;
void printBase(long long n, int m) {
if (n == 0) {
return;
}
printBase(n / m, m);
int x = n % m;
if (x < 10) {
cout << x;
} else {
cout << char('A' + x - 10);
}
}
void solve() {
long long n;
int m;
cin >> n >> m;
if (n == 0) {
cout << 0 << endl;
} else {
printBase(n, m);
cout << endl;
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
5. 过程举例
把 10 转成 2 进制：
10 / 2 = 5，余 0
5 / 2 = 2，余 1
2 / 2 = 1，余 0
1 / 2 = 0，余 1
余数从下往上看：
1010
递归正好可以先进入更小的 n / m，再回来输出余数。
七、记忆化递归
1. 为什么需要记忆化？
普通递归有时候会重复计算同一个子问题。
比如求斐波那契：
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
这里 fib(3) 被算了多次。
如果 n 更大，重复计算会更多。
2. 记忆化递归的概念
记忆化递归就是：
第一次算出某个子问题的答案后，把答案保存起来。
以后再遇到同一个子问题，直接拿出来用。
大纲中的意思是：
递归过程中发现某个子问题会被重复求解。
但第一次求解时，我们已经知道了它的答案。
所以把它保存起来，后面再需要时直接使用。
3. 记忆化斐波那契代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
long long memo[N];
long long fib(int n) {
if (n == 1 || n == 2) {
return 1;
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
void solve() {
int n;
cin >> n;
cout << fib(n) << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
4. memo[n] 的含义
memo[n] 表示 fib(n) 已经算出来的答案。
如果：
memo[n] != 0
说明以前算过，直接返回。
如果没有算过，就递归计算，并保存：
memo[n] = fib(n - 1) + fib(n - 2);
八、递推
1. 递推概念
递推就是：
先把小问题的答案求出来并保存，
再用已经知道的小问题答案推出大问题答案。
大纲中的说法是：
我们先把子问题的答案求出来并保存，
当我们要解决一个问题时，就用已知的子问题直接来求解。
2. 递归和递推的区别
| 方法 | 思考方向 | 简单理解 |
|---|---|---|
| 递归 | 大问题找小问题 | 要算 n，先去算 n-1 |
| 递推 | 小问题推出大问题 | 先算 1，再算 2，再算 3 |
递归像是：
从大问题一路问到小问题，再回来。
递推像是：
从最小的问题开始，一步一步往后算。
九、递推例题一：斐波那契
1. 递推式
斐波那契数列：
f[1] = 1
f[2] = 1
f[i] = f[i - 1] + f[i - 2]
其中：
f[i] 表示第 i 项的值。
2. 递推过程
先知道：
f[1] = 1
f[2] = 1
然后：
f[3] = f[2] + f[1] = 2
f[4] = f[3] + f[2] = 3
f[5] = f[4] + f[3] = 5
3. 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
long long f[N];
void solve() {
int n;
cin >> n;
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
cout << f[n] << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
4. 递推写法的优点
递推不会像普通递归那样重复计算。
它是：
每一项只算一次。
所以通常更快，也更稳定。
十、递推例题二：一个圆被 n 条直线最多切几份
1. 问题说明
一个圆，用 n 条直线去切，最多可以分成多少份？
先看小情况：
0 条线：1 份
1 条线：2 份
2 条线：4 份
3 条线：7 份
2. 为什么第 n 条线会增加 n 份？
假设已经有 n - 1 条线。
现在再画第 n 条线。
为了让增加的区域最多，第 n 条线要尽量和前面的 n - 1 条线都相交，而且交点不能重合。
这样第 n 条线最多会产生：
n - 1 个交点
这些交点会把这条新线分成：
n 段
每一段都会把原来的一个区域一分为二。
所以会增加：
n 个区域
3. 得到递推式
设：
f[n] 表示 n 条线最多把圆切成几份。
初始：
f[0] = 1
递推式：
f[n] = f[n - 1] + n
4. 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
long long f[N];
void solve() {
int n;
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] + i;
}
cout << f[n] << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
5. 表格理解
| 线的数量 n | 最多份数 f[n] | 新增份数 |
|---|---|---|
| 0 | 1 | - |
| 1 | 2 | 1 |
| 2 | 4 | 2 |
| 3 | 7 | 3 |
| 4 | 11 | 4 |
每次新增的份数正好是当前线的编号。
十一、本节课总结
1. 加法原理和乘法原理
分情况用加法。
分步骤用乘法。
2. 递归
递归就是：
函数调用自己，去解决更小的同类问题。
递归必须有：
递归出口；
递归关系。
3. 记忆化递归
记忆化递归就是：
把已经算过的子问题答案保存起来，下次直接用。
4. 递推
递推就是：
先算小问题，再一步一步推出大问题。
5. 递归和递推的联系
很多问题既可以递归，也可以递推。
例如：
斐波那契数列。
初学时可以先用递归理解问题，再用递推提高效率。
课后练习
练习 1：判断用加法还是乘法
- 早餐可以选 3 种包子或 2 种面包，只吃一种，一共有多少种选择？
- 上衣有 4 件，裤子有 3 条，选一件上衣和一条裤子，一共有多少种搭配？
练习 2：递归求和
输入 n，用递归求：
1 + 2 + 3 + ... + n
提示：
sum(n) = sum(n - 1) + n
sum(1) = 1
练习 3：最大公约数
输入两个整数 a 和 b，用递归求它们的最大公约数。
练习 4：斐波那契递推
输入 n，用递推求斐波那契数列第 n 项。
练习 5：圆被直线最多切几份
输入 n，输出一个圆被 n 条直线最多切成几份。
本节课最重要的五句话
- 分情况用加法，分步骤用乘法。
- 递归是函数调用自己解决更小的同类问题。
- 递归一定要有出口。
- 记忆化递归可以避免重复计算。
- 递推是从小问题一步一步推出大问题。
这里空空如也
有帮助，赞一个