XP02 DAY5 递归和递推学习笔记
一、加法原理和乘法原理
1. 为什么先讲这两个原理？
递归和递推经常会遇到：
如果是“分情况”，通常用加法原理。
如果是“分步骤”，通常用乘法原理。
2. 加法原理
加法原理用于：
它的特点是：
生活例子：
总选择数是：
因为“吃包子”和“吃面包”是两类不同情况。
3. 加法原理关键词
看到这些词，可以想到加法原理：
4. 乘法原理
乘法原理用于：
它的特点是：
生活例子：
总搭配数是：
因为每一件上衣都可以搭配每一条裤子。
5. 乘法原理关键词
看到这些词，可以想到乘法原理：
6. 加法和乘法的区别
原理 什么时候用 计算方式 加法原理 分情况，只选其中一种 相加 乘法原理 分步骤，每一步都要做 相乘
简单记：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、递归
1. 递归的概念
递归就是：
大纲中的说法可以这样理解：
2. 生活例子：排队问人数
你站在队伍最前面，想知道队伍一共有多少人。
你可以问后面的人：
后面的人也可以继续问他后面的人。
直到最后一个人，他知道：
然后答案一层一层传回来。
这就是递归的感觉：
3. 递归必须有两个部分
递归函数必须有：
递归出口：
递归关系：
如果没有递归出口，函数会一直调用自己，程序会出错。
4. C++ 中如何实现递归？
C++ 中递归的实现方式是：
例如：
这就是函数调用自己。
但是这个函数没有递归出口，会一直调用下去，是错误写法。
正确递归要有出口。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、递归例题一：斐波那契数列
1. 题目概念
斐波那契数列是：
它的规律是：
也就是：
2. 为什么适合递归？
要求第 n 项，需要先知道：
这两个问题和原问题一样，都是“求斐波那契数列的某一项”，只是规模更小。
所以可以递归。
3. 递归出口
当：
答案都是 1。
这就是递归出口。
4. 递归代码
5. 递归调用过程
求：
会变成：
最后遇到：
答案再一层层返回。
6. 重要提醒
普通递归写斐波那契很容易理解，但如果 n 很大，会很慢。
因为很多子问题会被重复计算。
例如：
这就引出后面的：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、递归例题二：最大公约数
1. 什么是最大公约数？
最大公约数就是：
例如：
2. 辗转相除法
大纲中给出的公式：
意思是：
其中 % 是取余。
3. 递归出口
当：
答案就是：
4. 代码
5. 过程举例
求：
过程：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、扩展：最小公倍数
1. 什么是最小公倍数？
最小公倍数就是：
例如：
所以：
2. 最大公约数和最小公倍数的关系
公式：
为什么先除再乘？
3. 代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、扩展：十进制转 M 进制
1. 问题说明
给一个十进制整数 n，把它转换成 m 进制。
例如：
2. 为什么可以递归？
我们可以先得到最后一位：
剩下的部分是：
要输出完整的 m 进制，就需要先输出 n / m 的结果，再输出最后一位。
所以递归关系是：
3. 递归出口
当：
就不用继续递归了。
4. 代码
5. 过程举例
把 10 转成 2 进制：
余数从下往上看：
递归正好可以先进入更小的 n / m，再回来输出余数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、记忆化递归
1. 为什么需要记忆化？
普通递归有时候会重复计算同一个子问题。
比如求斐波那契：
这里 fib(3) 被算了多次。
如果 n 更大，重复计算会更多。
2. 记忆化递归的概念
记忆化递归就是：
大纲中的意思是：
3. 记忆化斐波那契代码
4. MEMO[N] 的含义
如果：
说明以前算过，直接返回。
如果没有算过，就递归计算，并保存：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、递推
1. 递推概念
递推就是：
大纲中的说法是：
2. 递归和递推的区别
方法 思考方向 简单理解 递归 大问题找小问题 要算 n，先去算 n-1 递推 小问题推出大问题 先算 1，再算 2，再算 3
递归像是：
递推像是：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、递推例题一：斐波那契
1. 递推式
斐波那契数列：
其中：
2. 递推过程
先知道：
然后：
3. 代码
4. 递推写法的优点
递推不会像普通递归那样重复计算。
它是：
所以通常更快，也更稳定。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、递推例题二：一个圆被 N 条直线最多切几份
1. 问题说明
一个圆，用 n 条直线去切，最多可以分成多少份？
先看小情况：
2. 为什么第 N 条线会增加 N 份？
假设已经有 n - 1 条线。
现在再画第 n 条线。
为了让增加的区域最多，第 n 条线要尽量和前面的 n - 1 条线都相交，而且交点不能重合。
这样第 n 条线最多会产生：
这些交点会把这条新线分成：
每一段都会把原来的一个区域一分为二。
所以会增加：
3. 得到递推式
设：
初始：
递推式：
4. 代码
5. 表格理解
线的数量 n 最多份数 f[n] 新增份数 0 1 - 1 2 1 2 4 2 3 7 3 4 11 4
每次新增的份数正好是当前线的编号。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、本节课总结
1. 加法原理和乘法原理
2. 递归
递归就是：
递归必须有：
3. 记忆化递归
记忆化递归就是：
4. 递推
递推就是：
5. 递归和递推的联系
很多问题既可以递归，也可以递推。
例如：
初学时可以先用递归理解问题，再用递推提高效率。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
课后练习
练习 1：判断用加法还是乘法
1. 早餐可以选 3 种包子或 2 种面包，只吃一种，一共有多少种选择？
2. 上衣有 4 件，裤子有 3 条，选一件上衣和一条裤子，一共有多少种搭配？
练习 2：递归求和
输入 n，用递归求：
提示：
练习 3：最大公约数
输入两个整数 a 和 b，用递归求它们的最大公约数。
练习 4：斐波那契递推
输入 n，用递推求斐波那契数列第 n 项。
练习 5：圆被直线最多切几份
输入 n，输出一个圆被 n 条直线最多切成几份。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本节课最重要的五句话
1. 分情况用加法，分步骤用乘法。
2. 递归是函数调用自己解决更小的同类问题。
3. 递归一定要有出口。
4. 记忆化递归可以避免重复计算。
5. 递推是从小问题一步一步推出大问题。
