递归：如何用三行代码找到“最终推荐人”？

推荐注册返佣金的这个功能我想你应该不陌生吧？现在很多 App 都有这个功能。这个功能中，用户 A 推荐用户 B 来注册，用户 B 又推荐了用户 C 来注册。我们可以说，用户 C 的“最终推荐人”为用户 A，用户 B 的“最终推荐人”也为用户 A，而用户 A 没有“最终推荐人”。一般来说，我们会通过数据库来记录这种推荐关系。在数据库表中，我们可以记录两行数据，其中 actor_id 表示用户 id，referrer_id 表示推荐人 id。

为什么使用递归？递归的优缺点？

• 优点：代码的表达力很强，写起来简洁。

• 缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

关于走楼梯的思路解析：

• 走到第1级，有1种方法 ，直接走1

• 走到第2级，有2种方法 （1,1）（2）总共两种走法

• 走到第3级，有3种方法 （1,1,1）（1,2）（2,1）总共3种走法

• 走到第4级，有5种方法 （1,1,1,1）（1,1,2）（1,2,1）（2,1,1）（2,2） 总共5种

• 走到第5级，有8种方法 依次类推

以此类推，后面的总等于前面两级方法之和，现在使用递归和递推两种方法解决本问题

什么样的问题可以用递归解决呢？

• 问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。

• 问题与子问题，除了数据规模不同，求解思路完全一样

• 存在递归终止条件

递归常见问题及解决方案

警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。

警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。

调试递归:

1.打印日志发现，递归值。

2.结合条件断点进行调试。

参考：https://time.geekbang.org/column/article/41440