从这一关开始，我们将大量介绍递归，与其有关的问题有：
与树和二叉树相关的大部分问题 二分查找相关的问题 快速排序、归并排序相关的问题 所有回溯的问题 所有动态规划的问题 可见，递归是算法进阶的基础，是必须要掌握的内容。
这一篇，我们先重新理解一下递归的基本问题。
1. 递归的特征
递归，大部分人都知道怎么回事，但是代码就是写不出来，所谓”你讲的都对，但我 就是不会“。递归的本质仍然是方法调用，不过是自己调用自己，系统给我们维护了 不同调用之间的保存和返回等功能。
这种例子在现实中也有很多的，例如有一个笑话：
从前啊，有座山，山上有座庙，庙里有个老和尚和一个小和尚在讲故事，老和尚对小 和尚说：
从前啊，有座山，山上有座庙，庙里有个老和尚和一个小和尚在讲故事，老和尚对小 和尚说：
从前啊，有座山，山上有座庙，庙里有个老和尚和一个小和尚在讲故事，老和尚对小 和尚说：
········
再比如下面这张图：
如果看递归代码的结构，就像下面这个样子，前面的每一层都去一模一样地调用下一层，不同的只是输入和输出d的参数，这个递推过程是写递归的第一个核心问题。
当然这个过程不能一直持续下去，一定要在满足某个要求之后返回结果，否则的话，就会抛出"StackOverFlow"(栈溢出)的异常。
所有的递归都有两个基本特征：
理解这几条特征，可以辅助我们更好地理解递归，我们现在一条条来看：
【1】执行范围不断缩小
递归就是数学里的递推，设计递归就是努力寻找数学里的递推公式，例如阶乘的递推公式就是 f(n)=n*f(n-1)，很明显一定是要触底之后才能反弹。再比如斐波那契数列的递归公式为f(n)=f(n-1)+f(n2)，n也在不断缩小。这条规律可以辅助我们检查自己写的递推公式对不对。
再比如后面我们讲的青蛙跳台阶的递推公式为：f(n)= f(n-1) + f(n-2)，哎！怎么和斐 波那契数列一样？是的，就是一样。
范围缩小不一定只体现 n 的变化上，在树的递归中我们会大量使用类似这样的结构：
int leftDepth = getDepth
每递归一次，都将范围缩小到当前节点的左子树或者右子树，范围也是在不断缩小的。
【2】终止条件判断在递归调用的前面
递归之后可能还有终止条件，但是在执行递归之前，一定会有一个终止条件。这一条也可以帮助我们检查自己写的算法对不对。
为什么呢？看下面例子，很明显recursion()会不断调用自己，这样会一直递归下去，无法退出来，直到抛出堆栈溢出异常 (StackOverflowError)。
public void recursion(参数0) {
recursion(参数1);
if (终止条件) {
return ;
}
}
所以，任何递归方法在执行递归之前，一定会有一个终止条件。
实际一个方法里的递归调用可能不止一次，还会加一些逻辑处理，比如下面这样，但是终止的条件仍然在前面。
public void recursion(参数0) {
if (终止条件) {
return;
}
//可能有一些逻辑运算1
recursion(参数1);
// 可能有一些逻辑运算1
recursion(参数2);
// ......3
recursion(参数n);
// 可能有一些逻辑运算
}
这一特点启示我们，可以先考虑清楚什么情况下终止，而且相关代码要写在靠前位置的，之后再考虑递归的逻辑，这样可以降低编写的难度。
2. 如何写递归
明白了上面的道理，那么该怎么才能写出递归方法呢？
第一步：从小到大递推
递归该怎么写呢？递归源自数学里的归纳法，这个在高中数学中学过，大致就是你先猜测出存在递归关系，f(n)=δf(n-1)，然后你只要证明当n增加1时，f(n+1)=δf(n)也是成立就说明你的猜测是对的。不过，在算法里，我们写递归一般不需要证明，先选几个较小的值验一下，再选择几个比较大的验一下即可。
很明显，大部分从n=1，2，3或者只有一两个元素开始写最简单。例如斐波那契序列为 1 1 2 3 5 8，...，从n=3开始都满足f(n)= f(n-1) + f(n-2)，然后我们再选择某个比较大的n来验证即可。
我们仍然以阶乘和斐波那契数列为例来看。斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34….，即第一项 f(1) = 1,第二项 f(2) = 1…..，从第三项开始就满足：
f(n) = f(n-1) + f(n-2)
这就是我们要找的递归公式。
对于阶乘也是一样的：
n=1 f(1)=1
n=2 f(2)=2*f(1)=2
n=3 f(3)=3*f(2)=6
n=4 f(4)=4*f(3)=24
....
由此我们可以推测递推公式是f(n)=n*f(n-1)。
第二步：分情况讨论，明确结束条件
我们说过递归里终止条件一定是靠前的，而大部分递归的终止条件不过是n最小开始触底反弹时的几种情况。
对于阶乘，当 n = 1 时你就应该知道 f(1) = 1，也就是下面这样子：
// 算 n 的阶乘(假设n不为0)
int f(int n){
if(n == 1){
return 1;
}
}
有时候需要考虑的终止条件不止一个，例如斐波那契数列的递推公式f(n) = f(n-1) + f(n-2)里，如果n=2时会出现f(2)=f(1)+f(0)，很明显这里是没有f(0)的，所以我们要将n==2也给限制住，所以结束条件是这样的：
int f(int n){
if(n
