什么是递归
递归是一个神奇的编程方法，一方面，递归的代码非常简洁，写出来让人赏心悦目，另一面，虽然递归的思想很容易理解，我们却很容易编写出错误的递归代码。
递归的应用非常广泛，在数据结构中，对树的遍历、深度优先搜索等都会用到递归的思想，所以搞明白递归是非常重要的。
那么，什么是递归呢？
递归是一种编程思想，它通过不断调用自身并缩小问题的规模，当问题小到一定规模之后就会很容易的得到答案。（这其中包含了一个很重要的解决问题的思路：将大问题分解成小问题）
我们将使用递归的条件总结如下：
- 一个问题的解可以被分解成多个子问题的解
- 这个问题的子问题的求解过程和求解这个问题的思路完全相同（除了数据规模在缩小）
- 必须存在递归终止条件：当问题规模达到最小，往往可以直接获得答案。
在递归的求解过程中，可以分为以下两步：
- 将大问题分解为小问题，这一部分成为“递”。
- 小问题被解决，程序向大问题返回，这一部分称为“归”
编写递归的关键
递归的关键在于写出递推公式 和 找到递归终止条件
我们给出一个递归题目：走台阶问题：这里有 n 个台阶，你每次可以跨 1 个台阶或者 2 个台阶，请问走上这 n 个台阶有多少种走法？例如：如果有 2 个台阶，你可以选择 1，1 走上去，也可以 2 直接走上去。
分析这个题目，你会发现， n 个台阶的走法等于 n-1 个台阶 加上 n-2 个台阶的走法，这就为我们给出了递推公式：
f(n) = f(n-1)+f(n-2)
下面看终止条件：
当问题规模缩小，缩小成为上 1 个台阶 和上 2 个台阶，这时候问题就很简单了：1 个台阶只有 1 种走法 ； 2 个台阶有两种走法。我们可以将这作为终止条件，即：
f(1) = 1
f(2) = 2
将递推公式和终止条件结合，使用代码表现出来：
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
没错，这就是一个求 n 个台阶的走法，是不是简直太美？
所以，写出递推公式，找到终止条件就可以让你写出神奇的递归代码。
为什么递归难以理解
注意上面的例子，在思路清晰的情况下我们不会遇到任何问题，如果我们没有上面的引导，直接自己想这个问题，可能会陷入这样的坑：问题 A 可以分解成 B 和 C ，那 B 和 C 的问题又该如何解决？B 和 C 的子问题又该如何解决呢？
这就是使用递归的典型误区：你不仅在思考 A 如何分解，还尝试思考 A 的子问题如何分解，然后又思考 A 的子子问题该怎么办，这样下去，你就晕了。
所以要避开递归在思维上的坑，紧抓一个问题和它的子问题的关系即可（也就是递推公式），千万不要试图用人脑分析递归下的每一个步骤。
递归会带来的问题
递归的简洁让人叹服，但是它也会带来一系列的问题：
递归代码要警惕堆栈溢出
不难看出，递归函数通过不断调用自身达到解决问题的目的，这就会给我们带来隐患：对函数的过度调用可能带来堆栈溢出。如果堆栈溢出，那么程序很可能会难以运行。
解决这个问题的办法是：限制递归深度。但是这种做法不能完全解决问题，本着物尽其用的想法，你应该根据栈的剩余空间来确定深度，而实时计算栈的大小又让代码过于复杂。
递归代码要警惕重复计算
对走台阶的例子，我们可以看这样一个分解过程：
递归重复计算.jpg
你会发现，f(4),f(3)等函数被重复计算了，这会浪费许多资源。
解决办法：可以通过散列表保存计算结果，我们将代码更改如下：
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// hasSolvedList可以理解成一个Map，key是n，value是f(n)
if (hasSolvedList.containsKey(n)) {
return hasSolvedList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSolvedList.put(n, ret);
return ret;
}
递归代码的效率问题
递归的复杂度分析十分困难，但是我们依然有迹可循。
时间复杂度：递归通过不断调用函数进行计算，当这些函数的调用数量较大时，就会积聚成一个可观的时间成本。
空间复杂度：函数的调用会在内存栈中保存一次现场数据，在分析空间复杂度时，需要额外考虑这部分的开销。
警惕脏数据，它们可能造成无线递归
如果我们使用递归查询数据库，而数据库中存在脏数据，使得数据形成了环路，这就会造成无限递归。
解决办法：限制深度 & 检测环路
将递归代码改写为非递归代码
如果你有敏锐的观察力，你会发现递归实际上使用堆栈作为一个存储临时变量的“栈”，所以从理论上，所有的递归代码都可以修改为非递归代码，以走楼梯为例子，我们将其改写为非递归：
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i <= n; ++i) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
虽然这样可能会带来一些好处，但是这种思路实际上是将递归改为“手动递归”，本质并没有变，也没有解决前面说的某些问题，徒增了实现的复杂度。所以，修改递归代码只是我们的一个“可选项目”。
总结
- 递归是一种非常高效、简洁的编码技巧。
- 递归需要满足三个条件。
- 编写递归代码关键在于找到递推公式和终止条件。
- 递归代码虽然简洁高效，但是也有很多弊端：堆栈溢出、重复计算、函数调用耗时、空间复杂度高、无线递归...在编码中，一定要控制好这些副作用。
以上就是关于递归的所有内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论