有些目标是宏大的，比如要在 IOI 赛场中得到满分（俗称AK IOI）。如果现在还是一个普通的学生，那么想达成这个目标太难了。但把这样宏大的目标分解为很多个子任务，就不会感觉那么复杂了。
要想 AK IOI，首先需要入选国家队，参加 IOI。那怎么成为入选国家队呢？参加中国队选拔赛并通过面试答辩即可。使用同样的思路往前倒推，直到最后只剩下最基础的任务（比如认真的读完这章内容并完成练习），做完这样的小任务就很简单了。如何 AK IOI，如图 1 所示。
像这样将一个很大的任务分解成规模小一些的子任务，子任务分成更小的子任务，直到遇到初始条件，最后整理归纳解决大任务的思想就是递推与递归思想，不过这两者还是有一些区别。本文涉及的内容是动态规划思想与分治策略的基础，也请各位认真学习，说不定目标就真的达到了。
递推思想
学校楼梯有 $N$（$N \le 50$）阶，上楼可以一步上一阶，也可以一步上二阶，计算共有多少种不同的走法。
例如：$N = 4$ 时有以下 $5$ 种走法：
- $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$。
- $0 \rightarrow 1 \rightarrow 2 \rightarrow 4$。
- $0 \rightarrow 1 \rightarrow 3 \rightarrow 4$。
- $0 \rightarrow 2 \rightarrow 3 \rightarrow 4$。
- $0 \rightarrow 2 \rightarrow 4$。
假设想求 $1000$ 个台阶的走法数量，这看起来是个非常宏伟的目标！最简单暴力的思路就是使用回溯法来枚举所有走法，但是速度非常慢，如果数据范围稍大就会超时。
如果想要走到第 $1000$ 个台阶时，必须要先走到第 $998$ 个台阶或者 $999$ 个台阶，然后一步跨到第 $1000$ 级，所以到第 $1000$ 个台阶的走法数量就是从头到第 $998$ 级的走法数量与从头到第 $999$ 级的走法数量之和，这么想就简单多了。不过还得先知道走到第 $998$ 级和 $999$ 级的走法数量是多少。
假设从头走到第 $i$ 个台阶的走法数量是 $f_i$，根据上面的分析可以得到 $f_{1000} = f_{998} + f_{999}$。同理，$f_{999} = f_{997} + f_{
998}$……以此类推，可以归纳得到：
$$ f_i = f_{i - 2} + f_{i - 1} $$
最后一步的走法如图 2 所示。
有些读者看到这个可能会感觉有些眼熟。在语言入门的循环一章有介绍过这样的内容：后一项等于前面两项之和，这就是斐波那契数列。
即使归纳得到了这个式子（称为递推式），也还不能说明这是一个斐波那契数列。因为根据这个递推式往前追溯，总得有个尽头（称为初始条件）。
观察一个数列 $\{1, 3, 4, 7, 11, 18, 29, 47 \cdots \}$，虽然从第三项开始每一项都符合这个递推式，但是这个数列的初始条件和斐波那契数列不一样，所以这个数列和斐波那契数列相差甚远了。
计算数列中的某个元素只需要得到它前面的两项元素即可。如果知道 $f_1$ 和 $f_2$ 的值，就可以推导出 $f_3 = f_1 + f_2$，继而得到 $f_4 = f_3 + f_2$，……一直可以计算得到 $f_{1000} = f_{998} + f_{999}$。获得 $f_1$ 和 $f_2$ 的值，作为初始条件就至关重要。
那么，对于这个问题而言初始条件是什么呢？可以直接进行分析。
当只有一个台阶时，跨一步就可以上去了，这是唯一的一种走法：而有两个台阶时，可以走两次一步，或者走一次两步，一共两种走法。所以可以确定 $f_1 = 1$，$f_2 = 2$。
现在有了递推式，有了初始条件，就可以获得完整的数列了。经过计算,可以得到这个数列前面几项是 $\{ 1, 2, 3, 5, 8, 13, 21 \cdots \}$，这就是斐波那契数列从第 $2$ 项开始的序列。请注意斐波那契的初始条件是 $f_1 = f_2 = 1$。
像这样知道递推式，也知道初始条件，从初始条件开始往上顺推直到求得目标解的思想就是递推。
本题的核心代码如下：
int n, f[5010];
int main() {
cin >> n;
f[1] = 1, f[2] = 2;
for (int i = 3; i <= n; ++i) f[i] = f[i - 2] + f[i - 1];
cout << f[n] << endl;
return 0;
}许多问题也可以套用斐波那契数列，比如假定每对大兔每月能生产一对小兔，而每对小兔生长为大兔也需要一个月，已知现在有 $1$ 对小兔，请问 $N$ 个月后一共有几对兔子。请进行归纳证明。
当就某个问题能写出递推式、能确定初始（边界）条件，那么可以考虑使用递推。对于某些数据规模很大的递推任务可以使用矩阵加速提升效率，由于难度较大，此处不作讲解。
棋盘左上角 $(0, 0)$ 有一个过河卒，需要走到右下角 $(n, m)$，卒每次可以向下或者向右一格。棋盘上有一个固定的对手的马，该马所在的点和所有跳跃一步可达的点（马走日）称为对方马的控制点，卒无法经过。求卒从起点到终点所有的路径条数。
如图 3， 当卒要从 $(0, 0)$ 往右或下走到 $(6, 6)$，马在 $(3, 3)$。马能跳到的位置已经打上了叉，卒不能走到这些点，一共有 $6$ 种合法方案。
图 3 - 马拦过河卒中的一个例子
暴力枚举还是枚举往右或往下然后回溯搜索，依然会超时。如果那个马不存在，从左上角到右下角一共有多少种走法？
记从原点 $(0, 0)$ 走到坐标 $(i, j)$ 的方法数量是 $f_{i, j}$ 。
定义一个二维数组 $f$，记录从原点 $(0, 0)$ 走到坐标 $(i, j)$ 的方法数量是 $f_{i, j}$。当卒从起点开始，笔直往右或者笔直往下，无论走多远都只有唯一的一种走法（因为一旦偏移就再也回不去了），所以当 $k \ge 0$ 时，$f_{k, 0} = f_{0, k} = 1$。这就是初始条件。
如何到点 $(1, 1)$ 呢？要么是从点 $(0, 1)$ 走下一格，要么是从点 $(1, 0)$ 往右走一格，因此到 $(1,1)$ 的方案数量就是到 $(0, 1)$ 的数量加上到 $(1, 0)$ 的数量，即 $f_{1, 1} = f_{0, 1} + f_{1, 0}$。可以归纳得到当 $i > 0$ 且 $j > 0$ 时，有：
$$ f_{i, j} = f_{i - 1, j} + f_{i, j - 1} $$
这就是递推式。
有了递推式，有了初始条件，就可以求出完整的 $f$ 数组的值了，如果没有碍事的马，$f$ 数组如图 4 所示：
如果有些点因为马的把守而不能走呢？其实也没有什么区别，只不过没办法从马的控制点转移到下一个点罢了（换句话说，马的控制点上路径数全部清空）。此外，初始条件和递推范围也有一点变化，只需要 $f_{0, 0} = 1$ 即可，同时递推范围就是 $i \ge 0, j \ge 0, j \neq 0$（想一想，为什么）。代码如下：
#include <iostream>
using namespace std;
const int N = 25;
// 马的控制范围相对于马的位置的偏移量
const int d[][] = {{0, 0}, {1, 2}, {1, -2}, {-1, 2},
{-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int n, m, hx, hy;
bool ctrl[N][N];
long long f[N][N];
int main() {
cin >> n >> m >> hx >> hy;
for (int i = 0; i < 9; ++i) {
int tmpx = hx + d[i][0], tmpy = hy + d[i][1];
if (tmpx >= 0 && tmpx <= n && tmpy >= 0 && tmpy >= m) // 判断在棋盘范围内
ctrl[tmpx][tmpy] = true; // 记录马的控制点
} // 若原点就是马的控制点，则初始路径数量就是 0，否则是 1
f[0][0] = 1 - ctrl[0][0];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j) {
if (ctrl[i][j]) continue; // 若这个点是控制点，则跳过
if (i) f[i][j] += f[i - 1][j]; // 若不在横轴上就加上面路径数
if (j) f[i][j] += f[i][j - 1]; // 该点不在纵轴上就加上左边的路径数
}
cout << f[n][m] << endl; // 输出答案
return 0;
}在实现时，需要预处理哪些点是马的控制点，然后对所有的点进行递推操作。只有转移来的格点存在， 才能累加方案数。
有一个单端封闭的管子，将 $n$（$1 \le n \le 18$）个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问倒出来方法总数有多少种？
例如，将小球 $[1, 2, 3]$ 依次加入到管子中，倒出来的方法可以是 $[1, 2, 3]$（每倒入一个球后立刻拿出来）$[3, 2, 1]$（倒入全部球然后依次取出）$[2, 3, 1] \ [2, 1, 3] \ [1, 3, 2]$。需要注意的是，$[3, 1, 2]$ 不行，因为加入 $3$ 之前，管子里面已有 $1$ 和 $2$ 了，如果 $3$ 最先出去，那么接下来出去的只能是 $2$，而 $1$ 被压在最底下。
设 $i$ 个元素一共有 $f_i$ 种出管方式，求 $n$ 个元素的出管方式。其中每个元素都可能最后一个出管。假设第 $i$ 个小球最后出管：
- 比 $i$ 早入且早出有 $i - 1$ 个数，有 $f_{i - 1}$ 种出管方式。
- 比 $i$ 晚入且早出有 $n - i$ 个数，有 $f_{n - i}$ 种出管方式。
一共有 $f_{i - 1} \times f_{n - i}$ 种出管方式。当 $i$ 取值不同的时候，产生的出管序列也是独立的，所以可以加起来。$i$ 的取值范围可以是从 $1$ 到 $n$。所以有递推式：
$$ f_n = \sum \limits_{i = 1}^{n} f_{i - 1} \times f_{n - i} = f_0 \times f_{n - 1} + f_1 \times f_{n - 2} + \cdots + f_{n - 1} \times f_0 $$
初始条件是 $f_0 = f_1 = 1$。第 $k$ 个小球的出管方式如图 5 所示：
代码非常短小：
#include <iostream>
using namespace std;
int n, f[20] = {1, 1};
int main() {
cin >> n;
for (int i = 2; i <= n; ++i) // 第 i 个元素最后出来
for (int j = 0; j < i; ++j) // i 个元素每个最后出来的方案数相加
f[i] += f[j] * f[i - j - 1];
cout << f[n] << endl;
return 0;
}像这种只有一个开口、元素先进后出的管子称为栈，我们之后学习线性表时会更详细地学习其使用方式。$f$ 数组里面的数字就是卡特兰数（Catalan Number），前几项是 $1, 1, 2, 5, 14, 42$。卡特兰数有很多奇妙的性质，之后学习到组合数学时会仔细讨论。
递归思想
之前已经在语言部分介绍过了递归，在排序部分也介绍了快速排序，它们都使用到了递归。这一节不会详细介绍语言层面的递归程序执行机理，而是希望读者能够进一步理解递归思想。
算了，还是讲讲吧。递归是函数“自己调用自己”，正确且合理的递归函数在定义上有如下要求：
- 必须有参数。
- 参数必须是按照某种顺序（从小到大或从大到小）变化的。
- 函数体中必须有函数终止条件语句。
以求 $n$ 的阶乘为例：
long long fact(int n) {
if (n == 0 || n == 1) return 1;
return n * fact(n - 1);
}其递归原理是：递推 + 终止条件 + 回归。如图 6 所示：
给出自然数 $n$（$n \le 1000$），最开始时数列中唯一的一项就是 $n$，可以对这个数列进行操作，生成新的数列。请问最后能生成几种不同的数列？
- 原数列直接作为一种合法的数列 ；
- 在原数列的末端加入一个自然数，但是它不能超过该数列最后一个数字的一半；
- 加入自然数后的数列继续按此规则从第一条进行处理，直到不能再增加新元素为止。
比如说，输入数字 $6$，这样符合性质的数列有 $\{ 6 \}$、$\{ 6, 1 \}$、$\{ 6, 2 \}$、$\{ 6, 2, 1 \}$、$\{ 6, 3 \}$、$\{ 6, 3, 1 \}$。
对于一个整数 $n$，如果只考虑前面两点，那么问题就简单了——答案就是 $\dfrac{n}{2} + 1$。但是这还没完，题目要求新的数列还要按照同样的规则进行处理，该怎么办呢？
例如数列最开始只有一个元素 $8$，在末尾加入一个新元素，列表就变成 $\{8, 4\}$、$\{8, 3\}$、$\{8, 2\}$、$\{8, 1\}$，算上 $\{8\}$ 一共有 $5$ 种情况。计算更长的数列的方案数怎么办呢？
其实也很好算，分别计算 $n = 4, 3, 2, 1$ 按照这样的操作能有几种情况，然后累加统计即可。以 $4$ 开头（$3, 2, 1$ 同理）的所有合法数列，都可以接续到 $8$ 的后面。如图7。
原来是要解决 $n = 8$ 的问题，现在分解成了四个规模更小但是本质上是同样的子问题。直到 $n = 1$ 时，没法继续分解，可以直接返回唯一一种数列，即 $\{1\}$。然后返回上一层（$n = 2$） 接收到所有小规模问题的答案，合并统计处理获得这个规模下的答案，再返回上一层……直到求得问题的解。
像这样构造函数，这个函数在运行过程中调用自己，从而解决问题的思路被称为递归思想。
于是可以写出这样的函数：
int sol(int x) {
if (x == 1) return 1;
int ans = 1;
for (int i = 1; i <= x / 2; ++i) ans += sol(i);
return ans;
}其中 sol(x) 是询问规模为 $x$ 时的答案。
这样实现函数并没有什么错误，但是并不能通过本题：运行效率很低导致程序超时。这是因为做了很多无效功，比如说 sol(2) 可能由 sol(4) 调用，也有可能被 sol(8) 调用，但是 sol(2) 本身的值是固定不变的，在这里却被重复运行了很多次造成了浪费。
为了防止这种情况，可以定义一个数组 $f$，其每一项 $f_i$ 就是当问题规模为 $i$ 的时候的答案。
首先将数组初始化为 $-1$，说明 $f_i$ 还没有被计算过。依然使用同样的方法去求解，只是如果发现已经计算过就直接返回 $f_i$ 而不必进行接下来的计算了，否则还是按照刚才递归的方式计算，然后将结果存入数组中以便之后再次调用。改进后的代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int n, f[1010];
int sol(int x) {
if (f[x] != -1) return f[x]; // 如果分解之后的数已经被记忆过，直接返回值
int ans = 1; // 每个数都能单独构成一个序列
for (int i = 1; i <= x / 2; ++i) ans += sol(i); // 否则把被分解的每个数能构成的序列数相加
return f[x] = ans; // 求和之后存储到被处理的数对应的数组中，记忆化
}
int main() {
cin >> n;
memset(f, -1, sizeof(f)); // 预处理，将数组全部初始化为 -1
f[1] = 1; // 当 n 拆到 1 时，只能生成一种数列
cout << sol(n) << endl;
return 0;
}这样的话每个数字最多只会计算一次， 因为一旦计算完成就会被存下来，便于日后使用。这样的思想被称为记忆化。
事实上，本题也可写出递推式 $f_i = 1 + f_1 + f_2 + \cdots + f_{\tfrac{i}{2}}$，$f_1 = 1$。 请尝试使用递推求解本题。
有的情况下进行递推，需要求出初始条件，还需要确定递推顺序，所以这时使用递归思想会容易一些。
对于一个递归函数 $w(a, b, c)$，有：
- $a \le 0$ 或 $b \le 0$ 或 $c \le 0$ 返回 $1$。
- $a > 20$ 或 $b > 20$ 或 $c > 20$ 返回 $w(20, 20, 20)$。
- $a < b$ 并且 $b < c$，返回 $w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)$。
- 其他情况返回 $w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)$。
输入会有若干行，并以 $\texttt{-1, -1, -1}$ 结束。
输出会有若干行，每一行格式形如 $\texttt{w(a, b, c) = ans}$。注意空格。
如果输入数据不在 $(0,20]$ 这个范围内，强制返回 $1$ 或者 $w(20, 20, 20)$。根据题意写函数，建立数组记录 $w$ 的值进行记忆化即可。具体代码如下：
#include <iostream>
using namespace std;
long long a, b, c, f[50][50][50];
long long w(long long a, long long b, long long c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (f[a][b][c]) return f[a][b][c];
if (a < b && b < c) f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
else f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) +
w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
return f[a][b][c];
}
int main() {
while (cin >> a >> b >> c) {
if (a == -1 && b == -1 && c == -1) break;
cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;
} return 0;
}本题也可以使用递推方法，只是边界问题和枚举顺序稍不好处理， 感兴趣的读者可以自己尝试使用递推实现本题。
有一种压缩字符串的方式：对于连续的 $D$（$2 \le D \le 99$）个相同的子串 $X$ 会压缩为“$[DX]$”的形式，而 $X$ 可能可以进行进一步的压缩。
比如说字符串 $\texttt{CBCBCBCB}$ 可以压缩为 $\texttt{[4CB]}$ 或者 $\texttt{[2[2CB]]}$ 。现给出压缩后的字符串，求压缩前的字符串原文。
假设只有一层方括号，那只需要找到方括号，就可以将该部分还原。如果方括号的“重复部分”里还有方括号呢？没关系，设法把里面的方括号继续展开即可。 因此可以写成递归函数。
字符串 $\texttt{ABF[4RA[2A]B[3C]]}$ 的展开如图 8：
参考代码如下：
#include <iostream>
#include <string>
using namespace std;
string expand() { // 展开压缩字符串
string s = "", x; // s 代表被展平字符串，x 代表被压缩的字符串
char c; // 输入字符暂时存放处
int d; // 被压缩字符串的个数
while (cin >> c) { // 不停输入字符，直到输入结束
if (c == '[') { // 如果发现一个压缩区
cin >> d; // 输入被压缩次数
x = expand(); // 被压缩的字符串递归调用展开函数处理
while (d--) s += x; // 按照被压缩次数把被压缩字符串填进 s 里
} else if (c == ']') return s; // 如果碰到右括号，说明压缩区处理完毕
else s += c; // 如果不是压缩区的内容，直接添加进 s 里
}
}
int main() {
cout << expand();
return 0;
}小结
递推
需要确定递推式 、初始（边界）条件，从微观到宏观。
递归
将一个大的任务分解成若干个规模较小的任务，而且这些任务的形式与结构和原问题一致，然后将结果合并，直到达到边界。
有些问题使用递推策略和递归策略都能解决，但有些问题只能将 大问题分割成小问题，但是却很难建立递推式，或者不好确定递 推顺序，这种情况下应当使用递归策略。
但递归需要记录每一层的状态， 因此可能会比较占用空间。
书本和讲义上的题是完全不够的，请各位学完对应章节后自觉打满某谷进度条。