一、递归

递归算法是C++语言程序设计中一种重要的方法，它使得许多复杂的问题变得简单以及容易解决。

1. 递归概述

递归算法是C++语言程序设计中一种重要的方法，它使得许多复杂的问题变得简单以及容易解决。递归特点是函数或过程调用自己的本身，其中直接调用自己称为直接递归，而将A调用B，B调用A的递归叫做间接递归。常见问题有“汉诺塔问题”“Ackermann函数”等。

2. 汉诺塔问题

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问将n个圆盘从A移动到C需要操作多少次？（每次只能移动1个盘子，大盘子只能放在小盘子下面）

思路：

1. 当 n == 1 时，直接将盘子从 A 移动到 C，1次。
2. 当 n > 1 时，可以拆分成3大步骤：
   1. 将 n– 1 个盘子从 A 移动到 B，记为 f(n-1) 次。
   2. 将编号为 n 的盘子从 A 移动到 C，记为1次。
   3. 将 n– 1 个盘子从 B 移动到 C，记为 f(n-1) 次。

在此过程中，步骤①③ 明显是个递归调用，并且可以得到关系式： $f(n) = 1 \quad (n==1)$ $f(n) = 2 \cdot f(n-1) + 1 \quad (n>1)$

实现代码如下：

二、搜索与回溯算法

1. 概述

搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

回溯法也可以叫做回溯搜索法，它是一种搜索的方式，回溯是递归的副产品，只要有递归就会有回溯。

2. 深度优先搜索

深度优先搜索就是一条路走到底，当发现走不通的时候，就换一条路来走。深度优先的典型例题就是迷宫问题。

迷宫能否走通问题

一天小明在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n * n 的格点组成，每个格点只有2种状态，0和1，前者表示可以通行后者表示不能通行。同时当小明处在某个格点时，他只能移动到上下左右四个方向之一的相邻格点上，小明想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为1)，则看成无法办到。

输入格式：

• 第1行是一个正整数 n (1 ≤ n ≤ 100)，表示迷宫的规模是 n * n 的。
• 接下来是一个 n * n 的矩阵，矩阵中的元素为0或者1。
• 再接下来一行是4个整数 x1, y1, x2, y2，描述A处在第 x1 行、第 y1 列，B处在第 x2 行、第 y2 列。

输出格式：

• 能走到输出 YES，走不到输出 NO。

样例输入：

3
0 1 1
0 0 1
1 0 0
1 1 3 3

样例输出：

YES

3. 回溯

如果在搜索的过程中，发现此路不通或者走到终点还要找寻其他走到终点的方法，要返回到上一步，那么这种方法就叫做回溯算法。

迷宫所有路线问题

已知一 N×N 的迷宫，允许往上、下、左、右四个方向行走，且迷宫中没有任何障碍，所有的点都可以走。现请你按照右、下、左、上顺序进行搜索，找出从左上角到右下角的所有路径。

输入格式：

• 输入一个整数 N（N<=5）代表迷宫的大小。

输出格式：

• 按右、下、左、上搜索顺序探索迷宫，输出从左上角 1,1 点走到右下角 N,N 点的所有可能的路径。

样例输入：

3

样例输出：

1:1,1->1,2->1,3->2,3->3,3
2:1,1->1,2->1,3->2,3->2,2->3,2->3,3
3:1,1->1,2->1,3->2,3->2,2->2,1->3,1->3,2->3,3
4:1,1->1,2->2,2->2,3->3,3
5:1,1->1,2->2,2->3,2->3,3
6:1,1->1,2->2,2->2,1->3,1->3,2->3,3
7:1,1->2,1->2,2->2,3->3,3
8:1,1->2,1->2,2->3,2->3,3
9:1,1->2,1->2,2->1,2->1,3->2,3->3,3
10:1,1->2,1->3,1->3,2->3,3
11:1,1->2,1->3,1->3,2->2,2->2,3->3,3
12:1,1->2,1->3,1->3,2->2,2->1,2->1,3->2,3->3,3

三、阅读程序例题

1. 递归

（1）将第5行和第6行一起去掉，程序会出现死循环。（） {{ select(1) }}

• 对
• 错

（2）当输入的n,m的绝对值再在1000以内时，程序一定会正常运行。（错）
{{ select(2) }}

• 对
• 错

（3）若将该递归程序执行记忆化，则程序的时间复杂度为O(nm)。（）
{{ select(3) }}

• 对
• 错

（4）将第3行接在第9行后，则程序会编译错误。（）

{{ select(4) }}

• 对
• 错

（5）输入5 6，则输出为（）。

{{ select(5) }}

• 5
• 6
• 7
• 8

（6）输入2 4，则输出为（）。

{{ select(6) }}

• 6
• 6
• 7
• 8

【分析】本题可以通过递归转递推列表法，以n从小到大，m从小到大的顺序依次算出每个格子的值。由第7行可知，格子（n，m）的值可以通过格子（n-1，m），（n，m-1）和（n-1，m-1）的值得到。而边界的值，n0或m0的时候，可以通过第5行和第6行得到。

n/m	0	1	2	3	4	5	6
0		1	2	3	4	5	6
1		0	3	2	5	4	7
2		-1	4	1	6	3	8
3	0	1	2	3	4	5	6
4	1	0	3	2	5	4	7
5	2	-1	4	1	6	3	8

（1）第5行和第6行一起去掉后没有递归边界，故出现死循环。
（2）当输入的n,m均取负值，递归不会碰到递归边界，故出现死循环。
（3）将递归记忆化后，每个格点只会被访问一次，故程序时间复杂度为O(nm)。
（4）将第3行接在第9行后，n m从全局变量变为局部变量，不会导致程序编译错误。
（5）可以通过列表法求出，findans(5,6)=8。
（6）可以通过列表法求出，findans(2,4)=6。

深度优先搜索

（1）由于没有赋初始值，该程序会运行错误。（）
{{ select(7) }}

• 对

• 错 （2）如果将第18行去掉，程序结果会发生改变。（）
  {{ select(8) }}

• 对

• 错

（3）如果将第30行的ans<cnt改成ans<=cnt，输出结果会发生改变。（）

{{ select(9) }}

• 对
• 错

（4）该程序有可能输出114514。（）

{{ select(10) }}

• 对
• 错

（5）若输入为
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
则输出结果是（C）。

{{ select(11) }}

• 114514
• 1919810
• 7
• 8

（6）该程序的时间复杂度为（C）。

{{ select(12) }}

• $O(n)$
• $O(nlogm)$
• $O(n*m)$
• $O(mlogn)$

【分析】该代码的功能：输入一个nm的矩阵，求最大连通块的大小（连通块由0组成，1不构成连通块）。
（1）因为有cin输入赋值，所以程序不会报错。
（2）数组定义的是全局变量，初始值为0，因此可以不用再初始化为0。
（3）该程序要求的是最大值，因此小于改成小于等于不影响结果。
（4）因为数组开的100，所以最大连通块也不会超过10000。
（5）65的矩阵，填充9个1，画矩阵可得连通块最大为7。
（6）该代码会把每个点都搜索一遍，故时间复杂度是O(nm)。

3. 回溯

假设输入的n是不超过50的正整数，d[i][0]、d[i][1]都是不超过10000的正整数，完成下面的判断题和单选题：

（1）若输入 n 为 0,此程序可能会死循环或发生运行错误。（）
{{ select(13) }}

• 对
• 错

（2）若输入 n 为 20,接下来的输入全为 0，则输出为 0。（）
{{ select(14) }}

• 对
• 错

（3）输出的数一定不小于输入的 d[i][0] 和 d[i][l] 的任意一个。（）
{{ select(15) }}

• 对
• 错

（4）若输入的 n 为 20,接下来的输入是 20 个 9 和 20 个 0,则输出为（）。

{{ select(16) }}

• 1890
• 1881
• 1908
• 1917

（5）若输入的 n 为 30,接下来的输入是 30 个 0 和 30 个 5,则输出为 （）。

{{ select(17) }}

• 2000
• 2010
• 2030
• 2020

（6）若输入的 n 为 15，接下来的输入是 15 到 1，以及 15到1，则输出为（）。

{{ select(18) }}

• 2440
• 2220
• 2240
• 2420

【分析】程序输入了两个长度为n的序列A和B，分别保存到d[i][0]和d[i][1]；dfs求解A序列相邻项的和与B序列相邻项差的绝对值，求它们之和的最大值。

（1）n 为 0 时，dfs 中 for 循环不会被执行，因此直接输出 0，不会发生死循环。
（2）当两个序列同时为 0，dfs 中 sum 也始终为 0，则输出为 0。
（3）n = 1时，ans = 0，小于d[1][0] 和 d[1][1] 。

（4）对A序列进行迭代求和:

n	1	2	3	4	...	20
s	0	9+9=18	18+9=27	27+9=36	...	20*9=180
ans		0+18=18	18+27=45	45+36=81		29+39+49+...+209

ans = (2*9+20 * 9)*19/2 = 1881

（5）对B序列相邻项差进行迭代求和:

n	1	2	3	4	...	30
s	0	5-5=0	10-5=5	15-5=10	...	29*5-5=140
ans		0	0+5=5	5+10=15		15+25+35+...+285

ans = (1+28) * 28 * 5/2 = 2030

（6）A序列相邻项的和与B序列相邻项差的绝对值和的最大值:

n	1	2	3	4	...	n
ans	15+14=29	15+14+13=42	15+14+13+12=54	15+14+13+12+11=65	...	15×2+(15+14)×2+...+(15+14+...+2)×2

ans=15×2+(15+14)×2 + ... + (15+14+...+2) ×2 = (15 + 29 + 42 + 54 + 65 +75+84+92+99+105+110+114+117+119)×2 = 1120×2 = 2240

四、训练题

1. 下面的故事与X算法有着异曲同工之妙。

   从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚给小和尚将故事...

{{ select(19) }}

• 枚举
• 递归
• 贪心
• 分治

2. 阅读如下代码，x(8)一共调用了多少次x函数X。

{{ select(20) }}

• 6
• 7
• 8
• 9

3. 递归离不开的数据结构是X。

{{ select(21) }}

• 数组
• 链表
• 栈
• 队列

4. 递归函数中的形参是X。

{{ select(22) }}

• 自动变量
• 外部变量
• 静态变量
• 可根据需要自定义存储类型

5. 一个递归算法必须包括X。

{{ select(23) }}

• 递归部分
• 递归部分和终止条件
• 迭代部分
• 终止条件和迭代部分

6. X是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

{{ select(24) }}

• 回溯法
• 枚举法
• 动态规划
• 贪心法

7. 按照右手优先原则进行深度搜索，从A走到D的路线为X。

{{ select(25) }}

• ABCD
• AFED
• ABGFCID
• ABID

8. X是回溯法中为避免无效搜索采取的策略。

{{ select(26) }}

• 递归函数
• 剪枝函数
• 随机数函数
• 搜索函数