数据结构与算法-递归
本文为王争老师在『极客时间』中的课程《数据结构与算法之美》的学习笔记，想要学习原文的同学购买相关课程学习。如有侵权请联系作者删除。
如何理解递归？
在学习数据结构与算法的过程中一般都会遇到一个坎——递归。今天我们就来分析分析递归。 首先我们通过一个生活中的例子入手。假如你现在正在排队买票，前面有很多人，怎么才能知道你现在是第几号呢？这个时候就可以用递归了，你可以问你前面的人是多少号，在他的号数上加一即为你的号数。但是，前面的人也不知道自己是多少号啊，所以他再问他前面的人，这样一个一个的向前面问，直到问道队头的人，他说他现在是1号，然后这样就可以一个一个向后把数字传回来，直到你前面的人告诉你他是多少号，这样你就知道了你的位置了。 这个例子就是一个标准的递归求解问题的分解过程，一个一个向前问的过程就是"递"，一个一个向后传回来的过程就是"归"。基本上所有的递归问题都可以用公式表示出来。如上述例子的递归推导公式为：
f(n) = f(n-1) + 1，其中f(1) = 1f(n)表示你现状所在的位置（多少号）， f(n-1)表示你前面一个人所在的位置（多少号）， f(1)=1表示第一个人直到自己为1号。有了这个递推公式，我们就可以很轻松的将它改写为递归代码，如下所示：
public int f(int n){ if(n == 1) return 1; else return f(n-1) + 1;}递归需要满足的条件
从上述例子可以可以总结如下三个条件：
- 一个问题的解可以分解为几个子问题的解 什么是子问题？子问题就是数据规模更小的问题。如前面介绍的例子，想要直到自己在哪个位置，可以分解为前面的人知道他在哪个位置这样一个子问题。
- 子问题除了数据规模不同，求解思路完全一样 如前面介绍的例子，你求解自己在哪个位置的思路，和前面一个人求解他自己在哪个位置的思路是完全一样的。
- 必须存在一个递归终止条件 把问题分解为子问题，然后把子问题分解为子子问题，一层一层分解下去，需要终止条件结束这种循环。如前面的例子，队头的人不需要问其他人就知道自己为1号，也就是这里的
f(1)=1，这就是终止条件。
如何编写递归代码
理解递归的过程和递归需要满足的条件后，我们接下来想想如何才能写出递归代码来呢？对于递归代码的编写，最重要的是写出递归公式，找到递归终止条件。 下面我们看一看LeetCode上一个原题70.爬楼梯【题目链接】。对于第一步的走法把所有走法分为两类，一类是第一步走了1个台阶，另一类是第一步走了2个台阶。所以对于n个台阶的走法就是等于先走1个台阶后剩下的n-1个台阶的走法+先走2个台阶后剩下的n-2个台阶的走法。递归公式表示如下所示：
f(n) = f(n-1) + f(n-2) 接下来我们关心的就是递归终止条件了。当只有一个台阶时，只有一种走法，就不需要递归。因此 f(1)=1。这个递归终止条件足够吗？我们可以使用 n=2，和 n=3这样比较小的数来试验一下。 当 n=2时， f(2)=f(1)+f(0)，由于只有 f(1)=1这一个递归终止条件，无法将 f(2)求解出来。所以除了 f(1)=1这一个递归终止条件外，我们可以把剩余两个台阶时作为递归终止条件，即 f(2)=2作为递归终止条件。这样知道递归终止条件和递归公式后，我们就可以轻松写出递归代码了：
public int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);}总结：写递归代码的关键就是如何将大问题分解为小问题的规律，并基于此规律写出递归公式，并总结处递归终止条件，最后将递归公式和递归终止条件翻译成代码。
避开思维误区
对于排队买票的例子，递归调用只有一个分支，也就是说"一个问题只需要分解为一个子问题"，这时我们很容易弄清楚"递"的过程和"归"的过程，所以理解起来难度不大。但是，当我们面临一个问题有多个子问题的情况时，递归就没有那么好理解了。 就如爬楼梯的例子，我们人脑几乎没有办法将整个"递"的过程和"归"的过程每一步想得清清楚楚。计算机擅长做重复的事情，所以递归正是这样，而我们人脑更喜欢平铺直叙的思维方式，当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后一层一层返回，试图想弄清楚计算机每一步都是怎么执行的，这样很容易被绕进去。 对于递归代码，这种试图想清楚整个递和归过程的做法实际上是进入了一个思维误区。我们该如何去思考递归呢？ 如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归代码的注意事项
a.递归代码要警惕堆栈溢出
由于在函数调用时会使用栈来保存临时变量，每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。 那么该如何避免堆栈溢出呢？ 我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错。对于排队买票的例子，我们可以改造成下面这样子，就可以避免堆栈溢出了。为了代码简洁，有些边界条件没有考虑，比如 x<=0。
// 表示递归的深度int depth = 0;
public int f(int n){
if(depth > 1000) throw exception;
if(n == 1) return 1; else return f(n-1) + 1;}但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。
b.递归代码要警惕重复计算
我们在分析一下爬楼梯的例子，如果我们把整个递归过程分解一下的话，那就是这样的：
从图中，我们可以直观地看到，想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。
为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。 我们改写爬楼梯的代码如下所示：
public int climbStairs(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 res = climbStairs(n - 1) + climbStairs(n - 2); hasSolvedList.put(n, res);
return res;}除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题。
在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销，比如我们前面讲到的电影院递归代码，空间复杂度并不是 O(1)，而是 O(n)。
怎么将递归代码改写为非递归代码？
递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。 那我们是否可以把递归代码改写为非递归代码呢？比如刚才那个排队买票的例子，我们抛开场景，只看 f(x)=f(x-1)+1 这个递推公式。我们这样改写看看：
public int f(int n){ int res = 1; for(int i=2; i<=n; i++){ res += 1; }
return res;}同样，爬楼梯的例子改为非递归的代码如下所示：
public int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2;
int res = 0; int pre = 2; int prepre = 1;
for(int i=3; i<=n; i++){ res = pre + prepre; prepre = pre; pre = res; }
return res;}所有的递归代码都可以迭代的方式。因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决前面讲到的某些问题，徒增了实现的复杂度。