本讲内容
递归的定义
递归的特性
递归的写法
递归的应用
思考题：
推荐注册返佣金
某app，用户 A 推荐用户 B 来注册，用户 B 又推荐了用户 C 来注册。我们可以说，用户 C 的“最终推荐人”为用户 A，用户 B 的“最终推荐人”也为用户 A，而用户 A 没有“最终推荐人”。
推荐人信息表
给定一个用户 ID，如何查找这个用户的“最终推荐人”？
递归的定义
递归是一种应用非常广泛的算法（或者编程技巧）。
先回忆下有哪些算法的实现用到了递归？
比如 DFS 深度优先搜索、前中后序二叉树遍历等等。
函数或者方法自身调用自身则为递归。调用的过程成为递，返回的过程成为归
递归的特性
什么样的问题可以用递归来解决呢？
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
递归的优点是代码的表达力很强，写起来简洁。
但是缺点也比较多：如空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等
递归的写法
怎么写递归算法？
关键：写出递推公式，找到终止条件
算法题：
假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？
如果有3个台阶， 走法有：
1，1，1
1，2
2，1
我们先来写分析递推公式
可以根据第一步的走法把所有走法分为两类，第一类是第一步走了 1 个台阶，另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：
f(n) = f(n-1)+f(n-2)
确定递推公式后，接下来计算终止条件
当有一个台阶时，我们不需要再继续递归，就只有一种走法。所以 f(1)=1。
如果只有这一个终止条件，对于f (2) = f(1)+f(0)，无法求解，即要使得f(0)=1，但是f（0）实际是没有意义的，所以我们把f (2) = 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);
}
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归常见问题和解决方法
堆栈溢出
在讲栈的时候，我们讲到函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
解决方法：
限制递归调用的最大深度
但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。
代码重复计算
爬楼梯递归分析
如上图，f(3),f(4)都存在重复计算的情况
解决方法：
缓存已经计算过的数据
通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回
递归代码都是改为非递归代码
因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。
但这种做法实际是执行了“手动”递归，本质没有改变，反而徒增了时间复杂度
网友评论