特别提醒：第一题数据范围太大不但需要高精度而且递归会超时，会做即可
如果想要了解如何不超时 请耐心将题单简介看完
各位好啊，这里是某 CQ ！
这次的题单提前，因为根据了解，大部分C语言老师实际上已经讲过递归了。
某 CQ 也去听了课，根据上课的速度，某 CQ 感觉各位同学对递归可能是一知半解，还没有明白递归到底是干嘛用的。
某 CQ 决定提前拿出题单，选择上课提到的三个比较经典的问题，帮大家把上课内容再过一遍。
说到递归，我们肯定得从斐波那契数列讲起，这个可太经典了。
先把代码写在这里，具体解释在下面：
int f(int n) {
if (n == 1 || n == 2) {
return 1;
}
return f(n - 1) + f(n - 2);
}
在其中我们可以看到，函数自己调用了自己，虽然里面的参数好像不太一样。
这到底是什么意思呢？
我们可以更加形象地解释一下：
要推出斐波那契数列，我们肯定少不了前两项，于是：
f(1)、f(2)：我们知道自己是1
而当n ≥ 3时：
f(n)：我是多少？我不到啊？问问f(n - 1)和f(n - 2)
f(n - 1)、f(n - 2)：问问前两项
……
从最高层一层一层询问下去，直到达到边界，知道确定的答案之后，再一层一层回来，这便是递归的原理。
而我们如何去写递归，需要搞清楚两个关键点：
1、边界条件是什么：
就像斐波那契数列的第一和第二项一样，我们得有最小的问题的答案，才能一层一层递归，找出结果。如果没有边界，那我们面临的将是无穷无尽的鄙视链。
2、对于当前的问题，我们该怎么处理：
像斐波那契数列的第n项，我们不知道它是多少，但是我们能知道它由 n - 1 和 n - 2 两个子问题构成，所以我们想知道 f(n) ，只需要知道 f(n - 1) 和 f(n - 2) 就行了，至于它们两个是怎么求出来的，这实际上并不在我们的关心范围内。
注：这样做在时间上并不合理，比如说要想知道 f(6)，大家可以去算一算到底调用了多少次 f(3)。但是这对我们理解递归有很有效的帮助。
UPD：加入此类递归的一种优化方法。
（这次题目选炸了，忘记重新过一遍数据范围了OTZ，请各位饶了我吧）
有些同学可能做了这个题单发现有些题目递归来做特别容易超时，正是因为上述原因导致我们重复去求解了明明只需要求解一次的问题。
那么我们能怎么解决重复求解的问题呢？
诶，我每次求解出其中一个子问题就把它存到一个数组里边，下次需要就直接拿出来用，不就行了吗？
我们还是用斐波那契数列来举例子：
long long f[10005];
long long fib(int n) {
if (f[n] != 0) {
return f[n];
}
return f[n] = fib(n - 1) + fib(n - 2);
}
int main() {
f[1] = f[2] = 1;
int n;
scanf("%d", &n);
printf("%lld\n", fib(n));
}
这样我们便通过将已经求解过的答案存到一个数组里来避免同一个子问题的重复求解，从而能在相当于n次循环的时间内解决了这个问题。
某 CQ 将这种方法不太准确地称作递归的记忆化，这是一种还算很常用的用来避免重复求解子问题的优化方法。
希望同学们能够掌握这种用空间换时间的优化方法，毕竟，空间比时间更好掌握。（空间可以算，非常直观，而时间有的时候很难看出来有没有超）
下面来解决一个稍微难理解一点的：汉诺塔问题
我们先来找边界条件：
当起始柱子上只有一个盘子的时候，直接把它挪到终点柱子就好了。竟然这么简单，某 CQ 表示这非常的难以置信。
然后我们来找盘子为 n 层时的处理方法：
实际上我们可以把 n 层抽象成两层：最底下的一层和上面 n - 1 层，以方便我们将 n 的问题拆分成更小的同时又是方便解决的问题。
然后考虑两层：我们得先把上面那个盘子移到中间柱子上面，再把下面一个盘子移到终点柱子上，最后把中间柱子上的那个盘子移到终点柱子上，完成汉诺塔的位移。
所以我们怎么具体构造这个递归呢？先给代码后解释：
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
printf("%d:%c->%c", n, a, c);
}
else {
hanoi(n - 1, a, c, b);
printf("%d:%c->%c", n, a, c);
hanoi(n - 1, b, a, c);
}
}
先解释一下这个函数中各个参数的含义， n 自然不用说，表示 n 层，但是如果你将 a，b，c 认作是一柱二柱三柱那格局就小了，它们应该被称作起始柱子，中间柱子和终点柱子。在递归的过程中，这三个变量的表示的柱子实际上会不断变化，因为你在一些步骤中终点柱并不是最开始的那个终点柱：比如说两层的时候，你第一步是要移到中间柱上，而不是终点柱上，中间柱才是你这一步的终点柱。
首先用if特判解决掉最小的问题，我们直接输出移动方式就行了。
然后关键的在下面，对于 n 层，我们先将 n - 1 层从起始柱子通过终点柱子的帮助移到中间柱子去，这之后我们将最底下的那一层移到终点柱子上，这一步可以直接输出，最后我们将这 n - 1 层从中间柱子通过起点柱子的帮助，移到终点柱子上，这就是抽象为两层的汉诺塔问题的处理方法。
通过这样的处理，我们将n层的问题，转化成了一次移动和两次 n - 1 层的问题，这样层层缩小，最终变成一层的可以直接解决的问题。
实际上递归就是一种量变引起质变的方式，通过不断地解决小问题，总有一天你会发现，欸，大问题好像也就这么简简单单的解决了。
递归真的很好用。
最后我们来简单介绍一下归并排序，这个实际上比汉诺塔问题更加好理解。不过归并的过程略微有些烧脑，某 CQ 希望各位同学自己去写一写，找到自己的方法，某 CQ 会在题单中放一道经典的需要用归并排序的问题，并且某 CQ 会在接下来的讲解中一并讲掉这题是怎么做的（当然这只是解决那道题其中的一种方法）
归并排序，这个就不给代码了，同学们需要自己写一写，找到自己习惯的写法。
归并排序到底是什么意思？它又到底快在哪里呢？
我们先解释一下归并排序的具体原理：
归并排序的目的是通过二分将整个序列的排序分成两个小序列的排序，然后通过一种特定的合并的方法将两个有序的序列合成一个有序的序列。
再来具体解释一下，比如我们想要排序下标从1到n的一个数组，那么我们实际上需要排序下标 1 到 (n + 1) / 2 的数组和 (n + 1) / 2 + 1 到 n 的数组，然后将这两个数组合并成一个有序的数组。
通过这样以二分的方法将数组拆分，直到将数组拆成长度为1，那这个时候它本身就是有序的，非常好，不需要排序。
然后具体的合并方式实际上很好想，实现起来略有一些麻烦，某 CQ 留给大家自己去实现。
至于它为什么快呢？因为每一层递归，我们实际上等价于对整个数组循环一边，将它们两两合并，也就是循环了 n 次，而将这个数组二分我们只需要分 log2(n) 次就能将它分到最小，所以我们实际上只需要 n * log2(n) 次循环就能解决这个问题，比起冒泡排序和选择排序的 n * n 次循环就快上不少。
这样，同学们是不是对递归有了更深的理解？
开始做题吧！不过记得，递归的题目确实有点抽象，同学们需要通过一定量的练习才能掌握的差不多，这次题目的难度可能浮动有点大，因为确实有那么一点点难挑，同学们也许需要克服一点困难。
下面是归并排序的一个应用的讲解：
归并排序可以用来解决逆序对问题：
在一个数列中，存在 i < j, 同时 a[i] > b[j] 这时我们称 (i, j) 这个二元组为这个数列的一个逆序对。
显然冒泡排序可以解决这个问题，当我们需要交换两个相邻的数时，显然这两个数构成了一个逆序对，而将一个数组变为有序数组，我们一定要解决所有的逆序对才行。
但是冒泡排序太慢了，我们不想用它，怎么办？
归并排序来帮你！
当我们想要合并两个序列的时候，逆序对可以计算吗？
这个就给个提示，不具体讲了，留给有条件的同学们自己去思考，题单里有一道这个题，可以自己去写写看。
祝大家本周末以及下周的期中考试愉快！
提单链接：