什么是递归？一文读懂
一.什么是递归？
递归，就是在运行的过程中不断地调用自己。递归有两个过程，简单地说一个是递的过程，一个是归的过程。简单用代码来理解：
public void fun(参数) {
if (终止条件) {
return;
}
fun(参数);
(其他判断条件或语句);
}
在上边代码中，当第一次进入函数时，先判断是否符合终止条件，符合则直接结束函数，不符合入下一语句，调用自己重新进入下一层自身函数，(注意这是最外一层将不向下继续执行语句，外层卡在fun（参数处）)，这个调用自己进入自身函数的操作过程即为“递”的过程。假设进入下一层后符合终止条件，返回结果，此时之前进入自身函数执行完成返回最外一层函数，最外一层函数递归调用处得到结果，(即内层函数执行完成得到结果返回值)，这个过程即为“归”的过程。这时最外一层函数才能继续执行下一语句，直至函数运行完成。
二.判断递归使用的场景
1.大问题可以拆分为多个子问题。
2.原问题和拆分后的子问题除了数据规模不同，解决思路完全相同。
3.存在递归终止条件。
递归在线性数据结构中使用不太明显，迭代基本可以很容易地解决问题。
递归在非线性结构中非常重要，比如二叉树，回溯，典型的树形问题-九宫格字母组合
三.递归代码的写法，(一定要注意方法的语义)
递归必须具备两个条件，
一是有边界，即终止条件。
二是需要调用自己。
这两个条件缺一不可，并且其中终止条件语句必须在递归调用语句之前。如果顺序颠倒则递归函数会进入死循环，永远退不出来，会出现堆栈溢出异常(StackOverflowError)。
在递归函数中，终止条件可以不止一个，递归调用也可以通过一些逻辑语句分成好几个。
四.讲一个简单且经典的实例(我认为的)
青蛙跳台阶问题：一只青蛙要跳上n层高的台阶，一次能跳一阶，也可以跳2阶，请问这只青蛙跳上n层高的台阶有多少种跳法？
问题解决：这个问题有好几种解法，这里就讲递归方法，这个问题需要逆向思维，如果从第一个台阶就开始算，就比较难想到终止条件，以及递归调用方式。我们可以让青蛙下台阶，一次可以下一个，也可以下两个。这时我们可以知道：
当n=1时，只有一种方法。
当n=2时，有两种方法。
其n>2时，青蛙可以选择跳两层台阶，也可以选择跳一层台阶。
以上我们可以得到，终止条件为台阶剩下1或2层时可以直接得到结果，即为边界。当n>2时我们可以使用递归语句调用自身。这样就可以写出递归代码：
public int climbStairs(int n){
//终止条件
if(n == 1)
return 1;
if(n == 2)
return 2;
//递归调用,此时青蛙可以选择跳一阶也可以跳两阶，所以将两种情况相加起来
return climbStairs(n-1) + climbStairs(n-2);
