递归：如何用三行代码找到最终联系人

如何理解递归？

数据结构和算法有两个难点，一个是递归，一个是动态规划。
以在电影院看电影为例，如果你想知道你前面有多少排，于是你问前面一排的人，前面一排的人再继续问前面一排的人。

其中代表你想知道你自己再哪一排，表示你前面一排的人想知道自己是哪一排。
因此可以轻松的写出如下递归代码：

int f(int n){
        if (n == 1){
            return 1;
        }
        return f(n-1) + 1;
    }

递归需要满足三个条件

1. 一个问题乐意分解成几个子问题的解
子问题就是规模更小的问题，比如我们在电影院哪一排就可以分解成前一排、前前一排人在哪等子问题。
2. 这个问题分解之后的子问题，除了数据规模变小之外，求解思路完全一样
还是以电影院为例，我们分解的求前一排在哪这个问题他的求解思路是一样的，就是继续问前面一排人位置在哪。
3. 存在递归终止条件
如果不存在终止条件，递归会无限制的重复下去，永远没有结果。

如何编写递归代码？

写递归代码最关键的是写出递归公式，寻找终止条件。
举个例子，有n个台阶，我们每次可以跨一个台阶或者两个台阶，问走n个台阶有多少种走法。
在该问题中，可以分解为，我当前走了x台阶后，剩下的n-x台阶该怎么走这种子问题，其求解思路还是一样的，所以递归公式我们已经找到了，剩下的就是寻找终止条件。

当我们走到最后的时候，剩下一个台阶或者两个台阶。剩下一个台阶只有一种走法，剩下两个台阶有两种走法，等价于剩下零个台阶有一种走法。所以终止条件为

完整代码如下：

static int f(int n){
        if (n == 1 || n == 0){
            return 1;
        }
        return f(n-1) + f(n-2);
    }

写递归代码的关键是找出如何将大问题分解成小问题的递推公式，然后找到终止条件，最后将递推公式和终止条件翻译成代码。

但是我们是时候在想象递推过程的时候会感觉脑容量不够用，这个是正常的，就算大佬也会有这种感觉。
比如说A问题可以分解成B、C、D三个子问题，我们关系的不应该是这三个子问题如果再衍生九个子问题。而是应该想象如果这三个子问题已经解决了应该如何将其还原成原来的问题并解决，这就是递归公式的关键。

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

递归代码要警惕堆栈溢出

因为递归是不停的调用该方法，而在Java虚拟机中，每使用一个方法就会在虚拟机栈中添加一个栈帧，如果一直添加，就可能会出现堆栈溢出的问题。
我们可以通过在代码中限制递归调用的最大深度来解决这个问题。

static int depth = 0;
    
    static int f(int n){
        depth ++;
        if (depth > 1000) throw excption;
        if (n == 1 || n == 0){
            return 1;
        }
        return f(n-1) + f(n-2);
    }

但是这种做法不能够完全解决问题，最大允许的递归深度与当前线程中栈的剩余空间大小有关系，无法事先计算。如果实时计算就会增加代码复杂度影响可读性。

递归代码要警惕重复计算

还是以前面台阶的例子为例：

在递归过程中可能会进行很多次的重复计算。为了避免这种情况，我们可以每次计算的结果记录下来，等到后面需要使用的时候直接提取出来就行了。

static int depth = 0;

    static int f(int n){
        depth ++;
        if (depth > 1000) throw excption;
        
        if (n == 1 || n == 0){
            return 1;
        }
        
        //hasSolvedList可以理解成map
        if (hasSolvedList.containsKey(n)){
            return hasSolvedList[n];
        }
        
        int res = f(n-1) + f(n-2);
        hasSolvedList.add(n, res);
        return res;
    }

在时间复杂度上，因为递归调用时会有其他很多操作，这些函数调用的次数多的时候，这些操作也会消耗不可忽略的时间。此外，因为每次调用函数都需要增加一个栈帧，我们在分析空间复杂度的时候不能忘记这部分。例如前面电影院的空间复杂度就是而不是。
回到文章最初，如何通过三行代码找到最终联系人：

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