递归
递归需要满足三个条件：
- 一个问题的解可以分解为几个子问题的解
- 这个问题分解后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
递归算法最关键的是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲找到终止条件，最后将递推公式和终止条件翻译成代码。
编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归代码虽然简洁高效，但是，递归代码存在堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等问题。
递归代码要警惕堆栈溢出
函数调用会使用栈来保存临时变量，系统栈或者虚拟机栈空间一般不大，如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
可以使用定义一个全局变量统计递归次数并且当超过阈值时抛出异常的解决方法，但是最大允许的递归深度跟当前线程剩余的栈空间大小有关，当最大递归调用深度比较小，如10，50时，可以使用该方法，反之，并不适用。
递归代码要警惕重复计算
为了避免重复计算，可以使用散列表结构来保存已经求解过的值，当递归调用时，先查找判断散列表中是否已经求解过了，有则直接返回，没有就继续计算，这样避免了过多的重复计算问题。实例代码如下：
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 hasSovledList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSovledList.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 pre_pre = 1;
for (int i = 3; i <= n; ++i) {
ret = pre + pre_pre;
pre_pre = pre;
pre = ret;
}
return ret;
}
如何用三行代码找到最终推荐人
一个数据库表，每行包含用户ID:actor_id和推荐人ID：referrer_id,如下图所示：
再到最终的推荐人代码如下：
long findRootReferrerId(long actorId) {
Long referrerId = select referrer_id from [table] where actor_id = actorId;
if (referrerId == null) return actorId;
return findRootReferrerId(referrerId);
}
实际工作中，上面的代码可能无法工作，因为：
- 递归很深，造成堆栈溢出
- 数据库里边存在脏数据，需要处理由此产生的无限递归问题
上面的问题都可以用限制递归深度来解决，但是针对第二个问题更优的方法是通过检测环的存在来解决。
注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。
Note: Cover Picture