如何用三行代码找到“最终推荐人“

一 概述

推荐注册反佣金是近几年比较常见的功能，很多App都有这个功能。这个功能中，用户A推荐用户B来注册，用户B又注册了用户C来注册。此时的用户C的"最终推荐人"为用户A，用户B的"最终推荐人"也为用户A，而用户A没有"最终推荐人"。

一般来说，我们会通过数据库来记录这种推荐关系。在数据库中，我们可以记录两行数据，其中actor_id表示用户id，referrer_id表示推荐人id。

二 递归

递归是一种应用非常广泛的算法或编程技巧。存在很多数据结构和算法的编码实现都要用到递归，比如DFS深度优先搜索，前中后序二叉树遍历等等。

递归的需要满足的三个条件

1. 一个问题的解可以分解为几个子问题的解。
2. 这个问题于分解后的子问题，处理数据规模不同，求解思路完全相同。
3. 存在递归终止条件。

 递归的理解

如果一个问题A可以分解为若干子问题B，C，D，然后假设子问题B，C，D已经解决，在次基础上思考如何解决问题A。而且，你只需要思考问题A与子问题B，C，D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。

递归代码要警惕堆栈溢出

在函数调用的过程中会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不会很大。如果递归求解的数据规模很大，调用层数很深，一直压入栈，就会有堆栈溢出的风险。

为了避免堆栈溢出，我们可以通过代码中限制递归的最大深度的方式来解决这个问题，如递归调用超过一定的深度之后就不继续往下再递归，而是直接报错。但是这种做法并不能完全解决这个问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。

递归找到"最终推荐人"

存在两个问题

第一，如果递归很深，可能会有堆栈溢出的问题。

第二，如果数据库里存在脏数据，我们还需要处理由此产生的无限递归问题。当存在A的推荐人是B，B的推荐人是C，C的推荐人是A，这样就会发生死循环。

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-C-A这种"环"的存在。