前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课
以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。
在求解链表的问题时，经常会用到递归，并且之后的 DFS 深度优先搜索、前中后序二叉树遍历等，所以我们必须要了解递归。
1. 递归
去的过程叫"递"，回来的过程叫"归"，基本上，所有的递归问题都可以用递推公式来表示。
举个例子，看电影去时，不知道自己是第几排了，可以问前面一排的人他是第几排，只要在他的数字上+1，就可以了，但是前面的人也不清楚，所以他也问他前面的人，这样一排一排的问，直到问道第一排，第一排的人说我在第一排，然后一排一排的再把数字传回来，直到你前面的人告诉你他在哪一排，于是就知道答案了，我们用递推公式表示出来：
f(n) = f(n-1)+1，其中 f(1) = 1
改成递归代码如下：
int f(int n){
if(n == 1) return 1;
return f(n-1) + 1;
}
2. 递归需要满足的三个条件
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在
递归终止条件
写递归代码最关键的是写出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了。
比如上台阶的问题，每次可以跨 1 个或 2 个台阶，请问走 n 个台阶需要有多少种走法？
我们可以根据第一步的走法把所有走法分为两类，第一类是第一步走 1 个台阶，另一类是第一步走 2 个台阶，所以 n 个台阶的走法就等于先走 1 阶后，n-1个台阶的走法 加上先走 2 阶后，n-2个台阶的走法，用公式表达就是：
f(n) = f(n-1) + f(n-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);
}
写递归代码的关键就是：
- 1.找到如何将大问题分解为小问题的规律
- 2.并且基于此写出递推公式
- 3.然后再推敲终止条件
- 4.最后将递推公式和终止条件翻译成代码
另外，不要试图想清楚整个递和归的过程，人脑没办法都想清楚，如果一个问题A 可以分解为若干子问题 B C D，可以假设 B C D 已经解决，然后在此基础上思考如何解决问题 A，不需要一层一层往下思考子问题和子子问题的关系，要屏蔽掉细节。
只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系。
3. 注意事项
3.1 递归代码警惕堆栈溢出
递归就是自己调用自己，函数调用会使用栈来保存临时变量，每调用一次函数，都会将临时变量封装成栈帧压入内存栈，等函数执行完成返回时，才出栈。如果递归求解的数据规模很大，调用层次很深，就会有堆栈溢出的风险。
那么如何避免呢？
可以限制递归调用的最大深，递归调用超过一定深度之后，就不继续递归了，直接返回报错，比如电影院的那个例子：
// 全局变量，表示递归的深度。
int depth = 0;
int f(int n) {
++depth；
if (depth > 1000) throw exception;
if (n == 1) return 1;
return f(n-1) + 1;
}
如果最大深度比较小，可以用此种方法。
3.2 警惕重复计算
第二个上台阶问题的递归过程分分解图：
image.png
从图中可以看到，想要计算f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。
我们可以用散列表来解决这个问题，保存已经求解过的 f(k)，当递归调用到 f(k)时，如果之前已经求解过，则直接从散列表中取值，不需要重复计算，代码如下：
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;
}
在空间复杂度的计算上，递归调用一次就会在内存栈中保存一次现场数据，所以上面讲到的电影院的递归代码，空间复杂度为 O(n)。
递归优点：
- 表达力强
- 代码简洁
递归缺点：
- 空间复杂度高
- 有堆栈溢出风险
- 存在重复计算、过多函数调用导致耗时较多等问题
4. 递归改为非递归
所有的递归代码都可以改为迭代循环的非递归写法，递归本身就是借助栈来实现的，只不过使用的栈是系统或者虚拟机提供的。如果我们自己实现栈，手动模拟入栈、出栈过程，这样就可以了。
5. 总结
递归就是借助栈实现的，需要注意它的空间复杂度。
写递归代码先要写出递推公式，然后找出终止条件，再翻译成递归代码。
要注意堆栈溢出、重复计算、函数调用耗时多、空间复杂度高问题。
递归是需要配合其他数据结构来进行的，在以后的练习题中会经常遇到递归了。
网友评论