摘要：递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以，搞懂递归非常重要，否则，后面复杂一些的数据结构和算法学起来就会比较吃力
推荐用户注册领取佣金很多人都遇到过，很多 App 在推广的时候都是这个套路。「萧何」引荐「韩信」加入刘邦阵营，「韩信」又引荐了那些年上铺的兄弟「韩大胆」加入。我们就可以认为「韩大胆」的最终推荐人是「萧何」，「韩信」的最终推荐人是「萧何」，而「萧何」没有最终推荐人。
用数据库记录他们之间的关系，soldier_id 表示士兵 id，referrer_id 表示推荐人 id。
soldier_id reference_id韩信 萧何
韩大胆 韩信
那么问题来了，给定一个士兵 id，如何查找这个用户的「最终推荐人」，带着这个问题，我们正式进入递归。
递归三要素有两个最难理解的知识点，一个是 动态规划，一个是递归。
大学军训，都会经历过排队报数，报数过程中自己开小差看见了一个漂亮小学姐，不知道旁边的哥们刚说的数字，所以再问一下左边哥们刚报了多少，只要在他说的数字 + 1 就知道自己树第几个了，关键是现在你旁边的哥们 看见漂亮小学姐竟然忘记刚刚自己说的数字了，也要继续问他左边的老铁，就这样一直往前问，直到第一个报数的孩子，然后一层层把数字传递到自己。
这就是一个非常标准的递归求解过程，问的过程叫「递」，回来的过程交「归」。转换成递推公式：
f(n)=f(n-1) + 1, 存在 f(1) = 1
f(n) 表示自己的数字，f(n - 1) 表示前面一个人的报数，f(1) 表示第一个人知道自己是第一个报的数字。
根据递推公式，很容易的转换成递归代码：
public int f(int n) { if (n == 1) return 1; return f(n-1) + 1; }到底什么问题可以用递归解决呢？总结了三个必要元素，只要满足一下三个条件，就可以使用递归解决。
1.一个问题可以分解多个子问题
就是可以分解恒数字规模更小的问题，比如要知道自己的报数，可以分解『前一个人的报数』这样的子问题。
2.问题本身与分解后的子问题，除了数据规模不同，求解算法相同
『求解自己的报数』和前面一个人『求解自己的报数』思路是一模一样。
3.存在递归终止条件
问题分解成子问题的过程中，不能出现无限循环，所以需要一个终止条件，就像第一排或者其中任何一个知道自己报数的孩子不需要再询问上一个人的数字，f(1) = 1 就是递归终止条件。
如何编写递归代码其实最关键的就是 写出递推公式，找到终止条件，然后把递推公式转成 代码就容易多了。
再举一个「青蛙跳台阶」的算法问题，假设有 n 个台阶，每次可以跳 1 个或者 2 个台阶，走这 n 个台阶有多少种走法？
再仔细想想，实际上，根据第一步的走法可以把所有的走法分两类，第一类是第一步走了 1 个台阶，另一种是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后， n-1 个台阶的走法 + 先走 2 阶后， n-2 个台阶的走法。
f(n) = f(n-1) + f(n-2)继续分析终止条件，当只有一个台阶的时候不需要再继续递归，f (1) = 1。似乎还不够，假如有两个台阶呢？分别用 n = 2、n=3 验证下。f(2) = 2 也是终止条件之一。
所以该递归的终止条件就是 f(1) = 1,f(2) = 2。
f(1) = 1; f(2) = 2; f(n) = f(n-1) + f(n-2);根据公式转成代码则是
public int f(n) { if(n == 1) return 1; if(n ==2) return 2; return f(n-1) + f(n-2); }划重点了：写递归大妈的关键就是找到如何将大问题分解成小问题的规律，并且基于此写出递推公式，再推出终止条件，租后将地推公式和终止条件翻译成代码。
对于递归代码，我们不要试图去弄清楚整个递和归的问题，这个不适合我们的正常思维，我们大脑更适合平铺直叙的思维，当看到递归切勿妄想把递归过程平铺展开，否则会陷入一层一层往下调用的循环。
当遇到一个问题 1 可以分解若干个 2,3,4 问题，我们只要假设 2,3,4 已经解决，在此基础上思考如何解决 A。这样就容易多了。
所以当遇到递归，编写 代码的关键就是 把问题抽象成一个递推公式，不要想一层层的调用关系，找到终止条件。
防止栈溢出