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

Posted on | Post modified:
Words count in article: 1.3k | Reading time ≈ 4

问题提出

推荐注册返佣金这功能大家都不会陌生。在这个功能中，用户A推荐用户B，用户名注册之后又推荐了用户C。我们可以说，用户C的“最终推荐人”为A，用户的“最终推荐人”也为A，而用户A则没有推荐人。

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

基于这个背景，问题是，给定用户id，如何查找这个用户的最终”推荐人？

如何理解递归？

数据结构和算法中，两个最难理解的知识点，一个是 动态规划，另一个是 递归。

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

这里有一个很有趣的例子可以体现出递归背后的原理：

周末你带着女朋友出去电影院看电影，女朋友问你，咱们现在在第几排啊？电影院太黑了，看不清没法数，现在你怎么办？

别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。

我们用递推公式表示：

1
2
3
4
5
6
int f(int n) {
    if(n == 1) {
        return 1;
    } 
    return f(n-1) + 1;
}

递归需要满足的三个条件

  1. 一个问题的解可以分成几个子问题的解
  2. 这个问题与子问题处理数据规模不同其它的求解思路都一样
  3. 存在递归终止条件

如何编写递归代码？

如何写递归代码？写递归代码最关键的是 写出递推公式， 找到终止条件。

写递归应该要注意什么？

  1. 递归代码要警惕堆栈溢出。

在实际开发的过程中，编写代码时，我们会遇到很多问题，比如堆栈溢出。而堆栈溢出会导致系统崩溃。那么我们应该如何预防堆栈溢出呢? 我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
// 全局变量，表示递归的深度。
int depth = 0;
int f(int n) {
  ++depth；
  if (depth > 1000) {
    throw exception;
  }
  if (n == 1) {
    return 1;
  }
  return f(n-1) + 1;
}

但是，由于最大允许的递归深度和当前剩余的栈空间大小有关，我们实现无法计算。所以，如果最大深度比较小时可以用这种方法，否则这种方法不实用。

  1. 递归代码要警惕重复计算

为了避免重复计算，我们可以通过一个数据结构(比如散列表)来保存已经求解过的f(k)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int f(int n) {
  if(n == 1) {
    return 1;
  }
  if(n == 2) {
    return 2;
  }
  
  if(hasSolvedList.containersKey(n)) {
    return hasSolvedList.get(n);
  }
  
  int res = f(n-1) + f(n-2);
  hasSolvedList.put(n, res);
  return res;
}

如何将递归代码改成非递归代码？

递归有利有弊，递归代码的表达力很强，写起来简洁，但是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数会耗时较多等问题。所以，在实际开发的过程中，根据实际情况来选择是否需要使用递归的方式来实现。 

1
2
3
4
5
6
7
8
// 刚刚电影院的例子
int f(int n) {
  int res = 1;
  for(int i = 2; i <= n; ++i) {
    res = res + 1;
  }
  return res;
}

解答开篇问题

1
2
3
4
5
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，那就会发生死循环。

第一个问题可以用 限制最大深度来解决，当然第二个可以在递归的同时检测是否为‘环’。(具体哪种方法呢？后面老师讲到了再链接过来~)

课后问题

我们平常调试代码喜欢使用IDE的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，有什么好的调试方法？

@博金
调试递归：
1、打印日志
2、结合条件断点进行调试。
@涛
递归是什么？
递归就是用栈的数据结构，加上一个简单的逻辑算法实现了业务功能。

有问题？发送 issues 给我~

0%