递归：如何用三行代码找到 “最终推荐人”？
推荐注册返佣金的功能。用户 A 推荐用户 B 来注册，用户 B 又推荐了用户 C 来注册。我们可以说，用户 C 的 “最终推荐人” 为用户 A，用户 B 的 “最终推荐人” 也为用户 A，而用户 A 没有 “最终推荐人”。
一般来说，我们会通过数据库来记录这种推荐关系。在数据库表中，我们可以记录两行数据，其中 actor_id 表示用户 id，referrer_id 表示推荐人 id。
image
基于这个背景，提出问题：给定一个用户ID，如何查找这个用户的 “最终推荐人”？
一、如何理解 递归 ？
递归是一种应用非常广泛的算法（或编程技巧）。
那究竟什么样的问题可以用递归来解决呢？只要满足下面三个问题，就可以使用递归来解决。
递归需要满足的三个条件
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
二、如何编写递归代码？
写递归代码最关键的是 写出递推公式，找到终止条件。
如何编写递推公式？
举个两个例子：
假设你与女朋友一起去看电影，电影放映中你女朋友忽然问你：咱们做的是第几排啊，在不看票的情况下，电影院又比较黑看不清，你如何知道你是第几排呢？
分析一下，你只需要问前面的人是第几排，在他的数字上加一就可以了，那前面的人也不知道自己是第几排啊，所以他问他前面的人，这样一排排往前问，最后再一排排把数字传回来即可。
这就是一个非常标准的递归求解问题的分解过程，去的过程叫 递，回来的过程叫 归。基本上所有的递归问题都可以用 递推公式 来表示。上述例子对应的 递推公式：
//因为n=1时，也就是第一排的人是一定直到自己在第一排的
//所以 f(1)=1
//f(n) 表示你想知道自己在哪一排
//f(n-1) 表示前面一排所在的排数
f(n) = f(n-1) + 1
根据上述递推公式可以写出递归代码：
int f(int n){
if(n==1) return 1;
return f(n-1) + 1;
}
假设这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少
种走法？如果有 7 个台阶，你可以2，2，2，1这样上去，也可以1，2，1，1，2这样子上
去，走法有很多，那么如何用编程求得总共有多少种走法呢？
分析一下，根据第一步的走法，可以把所有走法分位两类，第一类是第一步走了 1 个台阶，另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于 先走 1 阶后 n - 1 个台阶的走法 加上 先走 2 阶后 n - 2 个台阶的走法，所以对应的 递推公式：
//递推公式
f(n) = f(n-1) + f(n-2)
//下面是边界情况
//还剩一个台阶有 1 种情况
f(1) = 1;
//还剩两个台阶有 2 种情况，1、1或者 2
f(2) = 2;
根据上述递推公式可以写出递归代码：
int f(int n){
if(n==1) return 1;
if(n==2) return 2;
return f(n-1) + f(n-2);
}
总结：
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式， 然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
三、需要注意的思维误区
上面有两个例子，一个电影院示例一个台阶示例。
对于电影院这种，一个问题分解成一个子问题，我们大脑一思考就出来了，但是对于第二个，台阶示例这种，一个问题，分解为若干个子问题的情况，那我们的人脑一般情况下要想把多个情况的 递 和 归 的过程一步步想清楚，那就有点难了。
计算机擅长做重复的事情，所以递归正和它的胃口。而我们人脑更喜欢平铺直叙的思维方式，当我们看到递归时，总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后在一层层返回，试图搞清楚计算机每一步怎么执行的，这样就很容易被绕进去。
那么对于递归代码，既然这种想清楚整个递和归的过程的做法是一个思维误区，那正确的思维方式是怎样的呢？
image
编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
四、递归代码要警惕堆栈溢出
在学习栈的时候，我们了解到函数调用会使用栈来保存临时变量，每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回后，才出栈。那么当调用层次很深的时候，一直压入栈，就会有堆栈溢出的风险。
那么如何避免出现堆栈溢出呢？
我们可以在代码中限制递归调用的最大深度（就是多少层）来解决这个问题。递归调用超过一定深度（比如1000）之后，我们就不继续往下再递归了，直接返回报错。
//电影院例子新版
//全局变量
int depth = 0;
int f(int n){
++depth;
if(depth > 1000) throw new XXXException();
if(n == 1) return 1;
return f(n - 1) + 1;
}
如果最大深度比较小，就可以使用这种方法，否则这种方法不是很实用，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算，如果实时计算，代码过于复杂，就会影响代码的可读性。
如果最大深度比较大，那么就要自己模拟一个栈，使用非递归代码实现。
五、递归代码要警惕重复计算
使用递归时，还会出现重复计算的问题，比如刚刚的第二个台阶的示例，如果把整个过程分解一下：
image
为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 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 hasSovledList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSovledList.put(n, ret);
return ret;
}
image
六、怎么将递归代码改为非递归代码？
递归有利有弊：
- 利：表达力强，写起来非常简洁
- 弊：空间复杂度高，有堆栈溢出风险，存在重复计算，过多的函数调用会耗时较多等。
在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。
将电影院的例子根据：f(n)=f(n-1)+1 改写递归代码：
int f(int n){
int result = 1;
for(int i = 2;i <= n;i++){
result = result +1;
}
return result;
}
同样，第二个例子也可以改为非递归的实现方式：
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;
}
七、解答开篇
如何找到 最终推荐人？
long findRootReferrerId(long actorId) {
Long referrerId = select referrer_id from [table] where actor_id = actorId;
if (referrerId == null) return actorId;
return findRootReferrerId(referrerId);
}
虽然非常简洁，三行代码就搞定了，但是在实际项目中，上述代码并不能工作，这里有两个问题：
- 如果递归很深，可能会有堆栈溢出的问题。
- 如果数据库里存在脏数据，我们还要处理无限递归问题。（A的推荐人是B，B的推荐人是C，C的推荐人是A）
- 可以使用限制递归深度来解决这两个问题。但是还有个更高级的处理方式，就是自动检测 A-B-C-A这种环的存在，如何检测呢？
image
网友评论