应用场景
很多APP都有推荐用户注册返佣金或奖励的功能。在这个功能中，用户A推荐用户B来注册，用户B又推荐用户C来注册。那么用户C的最终推荐人就为A，用户B的最终推荐人也为A，用户A没有最终推荐人。在数据库表中，可以记录两行数据，其中user_id表示用户ID，referrer_id表示推荐人ID。
那么，问题是，给定一个用户ID，如何查找这个用户的最终推荐人？
应用到的思想就是递归
如何理解递归
很多数据结构和算法的实现都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等。
一个生活中的例子，在电影院由于太黑，你看不清自己在第几排，但是又想知道，怎么办呢？问前一排的人，他的排数+1就是你的排数。但是前一排的人也看不清自己在第几排，他又通过问自己的前一排，就这样一直传递问下去，直到第一排的人说我是第一排，于是又一排一排把数字传回来。
这样一个过程就是递归求解问题的分解过程，去的过程叫递，回来的过程叫归。基本上，所有的递归问题都可以用递推公式来表示。
f(n) = f(n-1) + 1, 其中，f(1) = 1
什么样的问题能用递归来解决？
同时满足以下三个条件，就可用递归来解决。
-
一个问题的解可以分解为几个子问题的解。
子问题是指数据规模更小的问题
想知道你“自己在哪一排”，可以分解为“前一排的人在哪一排”这个子问题 -
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。
你求解“自己在哪一排”，与前面一排求解“自己在哪一排”的思路是相同的。 -
存在递归终止条件
问题分解为子问题，子问题再一层层分解下去，但是不能无限循环，必须有终止条件。
电影院第一排的人知道自己在哪一排，即f(1) = 1,这就是递归终止条件。
编写递归代码
关键点：写出递归公式，找到终止条件。
栗子
假设有n个台阶，每次可以跨1个台阶或者2个台阶，那么请问走完这n个台阶，共有多少种走法？
分析
可以根据第一步的走法把所有走法分为两类，第一类是，第一步走1个台阶；第二类是，第一步走2个台阶。
所以，n个台阶的走法就等于，先走1阶后，n-1个台阶的走法，加上，先走2阶后，n-2个台阶的走法。
公式表示为：
f(n) = f(n-1) + f(n-2)
有了递推公式还不够，再分析终止条件：当有1个台阶时，就只有一个走法，所以f(1) = 1。用小规模数试验一下，该终止条件是否合理，当n=2时，f(2) = f(1) + f(0)。发现f(2)没法求解，因为没给f(0)的值。可以给定f(0) = 0，表示走0个台阶有1种走法，但这不符合常识，因而可以直接给定f(2) = 2，表示走2个台阶有2种走法，要么一步1个台阶走，要么一次跨2个台阶。
这样再试验f(3) = f(2) + f(1)，可以得出结果并正确。所以，递归终止条件就为f(1)= 1, f(2) = 2。
最终公式
f(1)= 1
f(2) = 2
f(n) = f(n-1) + f(n-2)
递归代码
def climbStairs(self,n):
if n==1:
return 1
elif n==2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
Key
对于递归代码，试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。
正确的思维方式应该是:
如果一个问题 A 可以分解为若干子问题 B、C、D，就假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，编写递归代码的关键是，只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
注意问题
1 . 递归代码要警惕堆栈溢出。函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
解决思路：可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错。
2 . 递归代码要警惕重复计算。刚刚的例子中，就存在这个问题，比如要计算f(5)，就需要计算f(4)和f(3)，而计算f(4)，需要计算f(3)和f(2)，这个过程中f(3)就被计算了多次。
解决思路：通过一个数据结构（散列表）来保存已经求解过的f(i)。当递归调用到f(i)时，先查找这个值是否已经求解。若是，则直接从散列表中取值返回，避免重复计算。
修改栗子中的代码
def climbStairs(self,n):
hash_list = [0,1,2]
if n==1:
return hash_list[1]
elif n==2:
return hash_list[2]
else:
for i in range(3, n+1):
hash_list.append(hash_list[i-1] + hash_list[i-2])
return hash_list[n]
3 . 时间和空间成本很高。在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销，比如前面的电影院递归代码，空间复杂度并不是 O(1)，而是 O(n)。