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

傷城~ 2022-12-11 13:57 128阅读 0赞

## 一 概述 ##

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

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

![20201002194748506.png][]

## 二 递归 ##

递归是一种应用非常广泛的算法或编程技巧。存在很多数据结构和算法的编码实现都要用到递归，比如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这种"环"的存在。**

[20201002194748506.png]: /images/20221123/843e4be4aed441d78ff3c730c7862698.png

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

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关用三行Python代码提取视频音频

相关 1088 三人行（JAVA）

相关怎样找到很多牛人

相关 2021-05-15 递归：如何用三行代码找到“最终推荐人”

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

相关如何用几行Python代码实现邮件发送

相关三人行

相关令人纠结的两行代码

相关如何用 200 行 JavaScript 代码实现人脸检测？

相关 Day6 递归：使用三行代码找到推荐人