数据结构与算法之递归

推荐注册返佣金的这个功能在很多App中都有。在这个功能中，用户A推荐用户B来注册，用户B又推荐了用户C来注册。我们可以说，用户C的”最终推荐人“为用户A，用户B的”最终推荐人“也是用户A。而用户A没有”最终推荐人“。

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

基于这个背景，我的问题是，给定一个用户id，如何查找这个用户的”最终推荐人“？带着这个问题，我们来学习今天的内容。递归（Recursion）。

如何理解”递归“

递归从字面上理解，一个是“递“，一个是“归”，任何事情都能用递归公式来解决，用一个生活中的例子，在我们看电影的时候，我们要往第一排传一句话，又无法直接越过中间的人，我们只能往前面一个人传“递”，前一个人再往前一个人传“递”…这样一直传到第一个人之后，往回“归”。用递归公式来表示则是f(x)=f(x-1)+1。
递归有三个要素：
1.可以把一个大问题拆分为几个小问题
2.每一个问题除了规模不一致，解决方式是一致的
3.有终止条件

写递归代码的关键就是找到如何将大问题分解成小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最坏将递推公式和终止条件翻译成代码。

在编写递归代码时，我们要将它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

使用递归需要谨防栈溢出和重复计算，如果数据库里有脏数据，还需要防止出现无限循环

解答开篇：
如何找到最终推荐人？

long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

但上述代码在实际项目中并不能工作，为什么呢？

1. 如果递归很深，可能会有堆栈溢出的问题。
2. 如果数据库里存在脏数据我们还需要处理由此产生的无限递归问题。比如demo环境下数据库中，测试工程师为了方便测试，会人为的插入一些数据，就会出现脏数据。如果A的推荐人是B，B的推荐人是C，C的推荐人是A，这样就会发生死循环。

第一个问题可以用限制递归深度来解决；第二个问题也可以用限制递归深度来解决。但是，还有一个更高级的处理方法，就是自动检测A-B-C-A这种环的存在。