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

基于这个背景，给定一个用户ID，如何查找这个用户的“最终推荐人”？

1.关于递归

数据结构与算法，有两个最难理解的知识点，一个是动态规划，一个是递归。
递归是一中应用非常广泛的算法(或者编程技巧)，有很多数据结构与算法的编码实现都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等。
方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。

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

1)一个问题的解可以分解为几个子问题的解

子问题就是数据规模更小的问题。

2)这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

3)存在递归终止条件

把问题分解为子问题，子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，需要有终止条件。

3.如何编写递归代码

写递归代码最关键的是写出递推公式，找到终止条件，将递推公式转化为代码。
假如这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问这n个台阶有多少中走法？
如果有7个台阶，可以2，2，2，1这样上去，也可以1，2，1，1，2这样，走法很多，如何用编程求得总共有多少中走法？
想一下，实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶，另一类是第一步走了2个台阶。所以n个台阶的走法就等于先走1阶后，n-1个台阶的走法加上先走2阶后，n-2个台阶的走法。

1
f(n) = f(n-1) + f(n-2)

再来看终止条件。当有一个台阶时，我们不需要再继续递归，就只有一种走法，所以f(1)=1。然而，只有这一个是不够的。
n=2时，f(2)=f(1)+f(0)，如果递归终止条件只有一个f(1)=1，那f(2)就无法求解了，而f(0)是客观不可行的，所以要把f(2)=2作为一个终止条件，表示走两个台阶，有两种走法，一步走完或者分两步来走。
把递归终止条件和递推公式放到一起就是：

1
2
3
f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)

转化为递归代码：

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

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

当我们面对的是一个问题要分解为多个子问题的情况，递归代码就没那么好理解。像刚刚这个例子，人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚。计算机擅长做重复的事情，所以递归正合它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把递归坪铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。
对于递归代码，这种试图想搞清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。
如果一个问题A可以分解为若干子问题B、C、D，可以假设子问题B、C、D已经解决，在此基础上思考如何解决问题A。而且，只需要思考问题A和子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题和子子问题，子子问题和子子子问题之间的关系，屏蔽掉递归细节。

编写递归代码的又一关键，只要找到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑取分解递归的每个步骤。

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

为什么递归代码容易造成堆栈溢出？如何预防堆栈溢出？
函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
上面的例子，如果将系统栈或者JVM堆栈大小设置为1KB，在求解f(1999)时便会出现如下堆栈报错：

1
Exception in thread "main" java.lang.StackOverflowError

如何避免出现堆栈溢出？
声明一个全局变量，可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度(比如1000)之后，就不继续往下再递归了，直接返回报错。
但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，会影响代码的可读性。所以，如果最大深度比较小，比如10、50，可以用这种方法，否则这种方法并不是很实用。

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


从图中，可以看到，想要计算f(5),需要先计算f(4)和 f(3)，而计算f(4) 还需要计算f(3)，因此f(3) 就被计算了很多次，这就是重复计算问题。
为了避免重复计算，可以通过一个数据结构(比如散列表)来保存已经求解过的f(k)。当递归调用到f(k)时，先从中看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  // hasSolvedList 可以理解成一个 Map，key 是 n，value 是 f(n)
  if (hasSolvedList.containsKey(n)) {
    return hasSovledList.get(n);
  }
  
  int ret = f(n-1) + f(n-2);
  hasSovledList.put(n, ret);
  return ret;
}

在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

6.递归代码改写为非递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f(n)
{
	if(n == 1) return 1;
	if(n == 2) return 2;

	int ret = 0;
	int pre = 2;
	int prepre = 1;
	for(int i = 3; i <= n; i++)
	{
		ret = pre + prepre;
		prepre = pre;
		pre = ret;
	}
	return ret;
}
//刚好这个走台阶的问题类似斐波那契数列

抽象出递推公式、初始值和边界条件，用迭代循环实现改写。
是不是所有的递归代码都可以改写为这种迭代循环的非递归写法？
笼统地讲，是的。因为递归本身就是借助栈来实现的，因不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。
但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也没有解决前面讲到的某些问题，徒增了实现的复杂度。

如何找到“最终推荐人”

1
2
3
4
5
6
long findRootReferrerId(long actorId)
{
	Long referrerId = select referrer_id from [table] where actor_id = actorId;
	if(referrerId == null) return actorId;
	return findRootReferrerId(referrerId);
}

在实际项目中，这三行代码并不能工作，为啥？这里面有两个问题。
一，如果递归很深，可能会有堆栈溢出的问题。
二，如果数据库里存在脏数据，还需要处理由此产生的无限递归问题。比如demo环境下数据库中，测试工程师为了方便测试，会人为地插入一些数据，就会出现脏数据。如果A的推荐人是B，B的推荐人是C，C 的推荐人是A，这样就会发生死循环。
第一个问题，可以用限制递归深度来解决。
第二个问题，自动检测A-B-C-A这种“环”的存在。如何来检测环的存在？

思考：对于递归代码，有什么好的调试方法？

1.打印日志发现，递归值。
2.结合条件断点进行调试。