1.1 什么是递归
在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。
1.2 递归的三大要素
1、 这个函数的功能；
他要完成什么样的一件事，而这个，是完全由你自己来定义的。也就是说，我们先不管函数里面的代码什么，而是要先明白，你这个函数是要用来干什么。
private static int fun(int number) {
// to do something
}
2、 寻找递归结束条件；
递归在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件,否则进入死循环无法退出。因此，我们需要找出当参数满足条件时，递归结束，之后直接把结果返回。请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。
例如：当number =1时，满足条件，退出递归函数。
// 计算 number 的阶乘(假设number不为0)
private static int fun(int number) {
if(number == 1){
return 1;
}
}
3、 找出函数的等价关系式；
要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。
只要if语句为true，每个fun()调用都将执行statement1，然后再调用fun()，而不会执行statements2 。当前调用结束后，程序控制权将返回给调用它的fun()，而该fun()将执行其statements2部分，然后结束，并将控制权返回给前一个调用，依次类推。
// 计算 number 的阶乘(假设number不为0)
private static int fun(int number) {
// statements1
if (number == 1) {
return 1;
}
// statements2
return number * fun(number - 1);
}
- 动态图解
1.3 剖析递归
剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，…，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,…,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。
1.4 递归案例
-
一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶。问要跳上第 n 级台阶有多少种跳法？
-
条件1：跳上第 1 级台阶只有一种跳法：直接跳 1 级即可。
-
条件2：或者一次跳 2 级。
如果要跳到 n 级台阶只能从 从 n-1 或 n-2 级跳， 所以问题就转化为跳上 n-1 和 n-2 级台阶的跳法了，如果 f(n) 代表跳到 n 级台阶的跳法，那么从以上分析可得 f(n) = f(n-1) + f(n-2),显然这就是我们要找的问题与子问题的关系,而显然当 n = 1, n = 2， 即跳一二级台阶是问题的最终解，于是递推公式系为：
- 将递推公式用代码实现：
/**
* 跳 n 极台阶的跳法
*/
public static int jump(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return jump(n - 1) + jump(n - 2);
}
1.3 总结
1、 总结的解递归的三个步骤可以比较顺利的解开递归题，一些比较复杂的递归题我们需要勤动手，画画图，观察规律，这样能帮助我们快速发现规律，得出递归公式，一旦知道了递归公式，将其转成递归代码就容易多了；
2、 递归代码要警惕堆栈溢出：；
函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。可以用一个变量设置做多递归多少次，超过一定次数自己抛出异常。