第十二课 递推、递归与搜索——程序为什么会“自己调用自己”又为什么会“不断尝试”一、这一课到底学什么这一课有三个关键词递推 递归 搜索实际上它们之间有一条非常漂亮的逻辑已知前面的结果 ↓ 递推 ↓ 把大问题变成小问题 ↓ 递归 ↓ 如果有很多可能 ↓ 搜索所以这一课不是简单背三个定义而是要建立一个思维面对一个复杂问题我们能不能把它拆成更小的问题二、第一部分什么叫递推先给同学们一个生活例子。假设第1天有1只兔子第2天有2只第3天有3只……当然这只是一个非常简单的例子。我们真正关心的是如果我知道前面的结果能不能推出后面的结果这就是递推三、最简单的递推数列例如a1 1 a2 2 a3 3 a4 4我们可以发现a[n] a[n-1] 1所以a1 1 a2 a1 1 2 a3 a2 1 3 a4 a3 1 4这就是递推。四、递推最重要的两个东西任何递推题我们首先找① 初始条件例如a[1] 1;② 递推关系例如a[i] a[i-1] 1;所以可以记成递推 初始值 递推公式。五、用C写出来int a[100]; a[1] 1; for(int i 2; i 10; i) { a[i] a[i-1] 1; }计算a[1] 1 a[2] 2 a[3] 3 a[4] 4 ... a[10] 10这里有一个非常重要的程序阅读思想数组中的当前值可能依赖前面已经算好的值。六、经典递推斐波那契数列这是经典的例子。定义F1 1 F2 1从第三项开始Fn F(n-1) F(n-2)所以1 1 2 3 5 8 13 21 34 ...七、一步一步计算F1 1 F2 1 F3 F2 F1 1 1 2 F4 F3 F2 2 1 3 F5 F4 F3 3 2 5所以1 1 2 3 5八、C程序int f[100]; f[1] 1; f[2] 1; for(int i 3; i n; i) { f[i] f[i-1] f[i-2]; }看到f[i] f[i-1] f[i-2];我们会想到这是递推。九、递推和循环有什么关系有的同学会问老师递推是不是就是循环不是。它们是两个不同层次的概念。递推 一种描述问题的方法 for循环 一种程序实现方法例如for(int i3;in;i) f[i]f[i-1]f[i-2];就是用循环实现递推。十、递推的程序阅读方法以后看到a[1] ...; a[2] ...; for(...) { a[i] ... }不要马上看输出。第一件事把数列写出来。例如a[1]2; a[2]3; for(int i3;i6;i) a[i]a[i-1]a[i-2];直接列a1 2 a2 3 a3 5 a4 8 a5 13 a6 21答案就出来了。十一、第二部分什么叫递归现在问题变化了。假设老师说请计算5!我们知道5! 5 × 4 × 3 × 2 × 1但是我们可以换一种思路5! 5 × 4!而4! 4 × 3!继续3! 3 × 2!继续2! 2 × 1!这就是大问题变成小问题。十二、这就是递归思想我们可以定义f(n) n × f(n-1)但是必须告诉计算机到哪里停止所以f(1)1这叫递归终止条件十三、C代码int fact(int n) { if(n 1) return 1; return n * fact(n-1); }调用cout fact(5);十四、大家容易犯的错误很多同学会问fact(5)调用fact(4)fact(4)又调用fact(3)那不是永远调用下去了吗不会。因为有if(n 1) return 1;所以5 ↓ 4 ↓ 3 ↓ 2 ↓ 1 ↓ 停止这就是递归必须有出口。十五、递归的三要素以后看到递归程序我们可以检查三个问题① 自己调用自己了吗例如fact(n-1)② 问题规模变小了吗n → n-1③ 有没有终止条件if(n1)三个条件基本齐了才是一个正常的递归结构。十六、递归和第7课的“调用栈”连接起来还记得第7课吗我们讲过函数调用会进入调用栈。现在fact(5)调用fact(5) ↓ fact(4) ↓ fact(3) ↓ fact(2) ↓ fact(1)调用栈可以想象成fact(1) fact(2) fact(3) fact(4) fact(5)然后fact(1)返回fact(1) → 1于是fact(2) → 2 × 1 2 fact(3) → 3 × 2 6 fact(4) → 4 × 6 24 fact(5) → 5 × 24 120最终120所以第7课和第12课真正连起来了递归 ↓ 函数不断调用自己 ↓ 调用栈不断压入 ↓ 达到出口 ↓ 逐层返回十七、程序阅读递归题最重要的方法看到return n * f(n-1);不要在脑子里乱想。直接展开f(5) 5 × f(4) 5 × 4 × f(3) 5 × 4 × 3 × f(2) 5 × 4 × 3 × 2 × f(1) 5 × 4 × 3 × 2 × 1 120这就是递归展开法。十八、经典递归求和例如123...n可以定义sum(n) n sum(n-1)终止sum(1)1代码int sum(int n) { if(n 1) return 1; return n sum(n-1); }那么sum(5) 5 sum(4) 5 4 sum(3) 5 4 3 sum(2) 5 4 3 2 sum(1) 15十九、递推和递归的区别这个要搞清楚。递推递归核心思想前面的结果推出后面的结果函数自己调用自己常见实现for循环函数调用是否一定用函数不一定是是否需要终止条件有初始条件必须有递归出口典型例子数列阶乘、DFS一句话递推是“往前推”递归是“自己调用自己”。二十、一个非常重要的例子斐波那契的递归前面我们用递推f[n] f[n-1] f[n-2];现在写成递归int fib(int n) { if(n 2) return 1; return fib(n-1) fib(n-2); }计算fib(5)展开fib(5) ├── fib(4) │ ├── fib(3) │ └── fib(2) └── fib(3) ├── fib(2) └── fib(1)二十一、为什么这个程序很慢因为fib(3)被重复计算。例如fib(5)里面需要fib(4) fib(3)而fib(4)里面又需要fib(3)于是fib(3)算了很多次。随着 n 增大计算量会快速增加。这也正好联系前面第10课的时间复杂度。讲义把指数级复杂度O(2^n)列为常见复杂度之一并强调随着问题规模增大运行效率会明显下降。所以程序阅读题如果出现这种递归f(n-1)f(n-2)一定要警惕可能产生大量重复计算。二十二、第三部分什么是搜索现在进入本课第三个核心。假设有一个迷宫S . # . . . # . # . . . . . . T从S走到T我们不知道哪条路能走通。怎么办一条一条尝试。这就是搜索。二十三、搜索和枚举有什么关系我们以前学过枚举。比如1~100全部试一遍。搜索也是尝试所有可能。但是搜索通常会更聪明尝试 ↓ 发现不可能 ↓ 立即回来 ↓ 换另一条路这叫回溯。二十四、DFS深度优先搜索DFS 的基本思想从起点开始访问如果某个邻接点没有访问过就继续深度遍历如果已经访问则继续寻找其他邻接点。讲义把它概括为“仿树的先序遍历过程”。对于小学生我们可以简单记成一条路走到底。例如A ├── B │ ├── D │ └── E └── CDFSA ↓ B ↓ D ↓ 回来 ↓ E ↓ 回来 ↓ C访问顺序可能是A B D E C二十五、为什么DFS经常和递归放在一起因为走到一个点 ↓ 继续走下一个点 ↓ 继续走 ↓ 继续走非常适合dfs(next);例如void dfs(int x) { vis[x] true; for(int y : graph[x]) { if(!vis[y]) dfs(y); } }看到dfs(y);孩子应该马上想到这是递归。所以DFS ↓ 递归 ↓ 调用栈这又把前面几课连接起来了。二十六、DFS为什么需要visited假设图A —— BA能走B。B又能走A。如果没有记录A → B → A → B → A → B...就会无限循环。所以vis[x] true;表示这个地方我已经来过了。以后再次遇到它if(!vis[y])就不再进去。二十七、DFS的核心思想给孩子一句口诀DFS一条路走到底走不通就回来。这里的“回来”就是回溯。二十八、BFS广度优先搜索上一课我们已经提前认识过BFS。讲义把 BFS 概括为仿树的层次遍历过程。先访问起始点的邻接点再访问这些点没有访问过的邻接点逐层向外扩展。所以BFS 一层一层地搜索。例如A / \ B C / \ / \ D E F GBFSA ↓ B C ↓ D E F G访问顺序A B C D E F G二十九、DFS和BFS对比DFSBFS中文深度优先搜索广度优先搜索思路一条路走到底一层一层走常见实现递归/栈队列记忆方式深广是否回溯常见通常不靠递归回退典型用途遍历、连通块、枚举最短步数、分层搜索BFS是分层搜索不像DFS那样有回退因此BFS算法不是采用递归过程。三十、为什么BFS使用队列假设第一层 B C我们必须先处理B C然后才能处理D E F G这正好是先进先出。所以BFS ↓ Queue而DFS ↓ Stack / 递归调用栈形成一个非常漂亮的对应关系DFS → 栈 → 后进先出 BFS → 队列 → 先进先出三十一、程序阅读题看代码void dfs(int x) { cout x ; vis[x] true; for(int y : g[x]) { if(!vis[y]) dfs(y); } }如果A的邻接点B、C B的邻接点D C的邻接点E从A开始dfs(A)执行输出A然后找到Bdfs(B)输出B然后dfs(D)输出DD结束以后回到B。B结束以后回到A。再走CC然后EE所以A B D C E三十二、初赛遇到DFS程序怎么办不要直接看答案。一定画搜索树。例如A / \ B C | | D E然后按照程序规定的邻接顺序走A → B → D → 回来 → C → E这就是程序模拟。三十三、初赛遇到递归程序怎么办采用“四步法”。第一步找出口例如if(n1) return 1;第二步找自己调用自己的地方f(n-1)第三步从大到小展开f(5) f(4) f(3) f(2) f(1)第四步从下往上算返回值f(1)1 f(2)2 f(3)6 f(4)24 f(5)120三十四、初赛遇到递推程序怎么办采用“列表法”例如a[1]2; a[2]3; for(int i3;i6;i) a[i]a[i-1]a[i-2];直接列i 1 2 3 4 5 6 a[i] 2 3 5 8 13 21比在脑子里算可靠得多。三十五、初赛遇到DFS怎么办采用“搜索树法”例如1 / | \ 2 3 4 / \ 5 6从1开始DFS1 ↓ 2 ↓ 5 ↓ 回来 ↓ 6 ↓ 回来 ↓ 3 ↓ 4得到1 2 5 6 3 4三十六、初赛遇到BFS怎么办采用“分层法”例如1 / | \ 2 3 4 / \ 5 6分层第0层1 第1层2 3 4 第2层5 6所以BFS 1 2 3 4 5 6三十七、一个非常重要的“最短路”思想假设迷宫每走一步费用 1从起点开始第0层起点 第1层走一步能到的位置 第2层走两步能到的位置 第3层走三步能到的位置那么第一次到达终点时走的步数就是最短步数。这就是BFS非常经典的用途。三十八、递推、递归、DFS、BFS终于串起来了算法 │ ┌─────────┴─────────┐ ↓ ↓ 递推 搜索 │ │ 前面的结果 很多可能性 推出后面的结果 │ │ ┌──────┴──────┐ ↓ ↓ DFS BFS │ │ 递归 队列 │ 栈同学们开始发现前面学的知识不是一个个孤岛而是在慢慢形成一张知识网络。三十九、CSP-J本课必背知识建议让孩子最后只记住下面这些。① 递推用前面已经知道的结果推出后面的结果。核心初始条件 递推关系② 递归函数直接或间接调用自己。必须有递归出口 规模不断变小③ DFS深度优先搜索。口诀一条路走到底走不通就回来。常见递归 栈④ BFS广度优先搜索。口诀一层一层向外扩展。常见队列四十、课堂练习第1部分递推 递归知识递推定义 ↓ 递推数列 ↓ 斐波那契 ↓ 递归 ↓ 递归出口 ↓ 递归展开 ↓ 调用栈重点题型根据递推公式求第N项阅读递推程序求输出阅读递归函数求返回值判断递归调用次数判断递归是否会终止第2部分DFS BFS知识搜索 ↓ DFS ↓ 递归 ↓ 回溯 ↓ BFS ↓ 队列 ↓ 分层搜索重点题型判断DFS/BFS写搜索顺序根据程序模拟访问顺序判断使用栈还是队列简单迷宫/图遍历四十一、给孩子的“终极口诀”递推看前面后面一步步推出。递归看自己自己调用自己。递归一定找出口出口不找容易绕。DFS往深处走走不通再回来。BFS一层一层走队列保证先进先出。DFS常用栈BFS常用队列。程序阅读不要靠猜递推列表、递归展开、DFS画树、BFS分层。