什么是递归？递归的理解

一.什么是递归？

        递归，就是在运行的过程中不断地调用自己。递归有两个过程，简单的说一个是递的过程，一个是归的过程。简单用代码来理解：

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);
}