企业官网建设流程全解析

第十二课 递推、递归与搜索

——程序为什么会“自己调用自己”，又为什么会“不断尝试”？

一、这一课到底学什么？

这一课有三个关键词：

递推 递归 搜索

实际上它们之间有一条非常漂亮的逻辑：

已知前面的结果 ↓ 递推 ↓ 把大问题变成小问题 ↓ 递归 ↓ 如果有很多可能 ↓ 搜索

所以这一课不是简单背三个定义，而是要建立一个思维：

面对一个复杂问题，我们能不能把它拆成更小的问题？

二、第一部分：什么叫递推？

先给同学们一个生活例子。

假设：

第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 i=3;i<=n;i++) f[i]=f[i-1]+f[i-2];

就是：

用循环实现递推。

十、递推的程序阅读方法

以后看到：

a[1] = ...; a[2] = ...; for(...) { a[i] = ... }

不要马上看输出。

第一件事：

把数列写出来。

例如：

a[1]=2; a[2]=3; for(int i=3;i<=6;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(n==1)

三个条件基本齐了，才是一个正常的递归结构。

十六、递归和第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

这就是：

递归展开法。

十八、经典递归：求和

例如：

1+2+3+...+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

十九、递推和递归的区别

这个要搞清楚。

一句话：

递推是“往前推”，递归是“自己调用自己”。

二十、一个非常重要的例子：斐波那契的递归

前面我们用递推：

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 └── C

DFS：

A ↓ 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 —— B

A能走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 G

BFS：

A ↓ B C ↓ D E F G

访问顺序：

A B C D E F G

二十九、DFS和BFS对比

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

然后找到B：

dfs(B)

输出：

B

然后：

dfs(D)

输出：

D

D结束以后回到B。

B结束以后回到A。

再走C：

C

然后E：

E

所以：

A B D C E

三十二、初赛遇到DFS程序怎么办？

不要直接看答案。

一定画：

搜索树。

例如：

A / \ B C | | D E

然后按照程序规定的邻接顺序走：

A → B → D → 回来 → C → E

这就是程序模拟。

三十三、初赛遇到递归程序怎么办？

采用“四步法”。

第一步：找出口

例如：

if(n==1) 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 i=3;i<=6;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开始DFS：

1 ↓ 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部分：递推 + 递归

知识：

递推定义 ↓ 递推数列 ↓ 斐波那契 ↓ 递归 ↓ 递归出口 ↓ 递归展开 ↓ 调用栈

重点题型：

1. 根据递推公式求第N项

2. 阅读递推程序求输出

3. 阅读递归函数求返回值

4. 判断递归调用次数

5. 判断递归是否会终止

第2部分：DFS + BFS

知识：

搜索 ↓ DFS ↓ 递归 ↓ 回溯 ↓ BFS ↓ 队列 ↓ 分层搜索

重点题型：

1. 判断DFS/BFS

2. 写搜索顺序

3. 根据程序模拟访问顺序

4. 判断使用栈还是队列

5. 简单迷宫/图遍历

四十一、给孩子的“终极口诀”

递推看前面，后面一步步推出。

递归看自己，自己调用自己。

递归一定找出口，出口不找容易绕。

DFS往深处走，走不通再回来。

BFS一层一层走，队列保证先进先出。

DFS常用栈，BFS常用队列。

程序阅读不要靠猜，递推列表、递归展开、DFS画树、BFS分层。