什么是递归？
斐波那契数列
在讲解递归前，还是聊聊经典的斐波那契数列。
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
这个数列从第3项开始，每一项都等于前两项之和。
求解数列中第n个数是多少？
分析：
n=1 -> 1
n=2 -> 1
n=3 -> 1+1 = 2
n=4 -> 2+1 = 3
n=5 -> 3+2 = 5
假设f(n)为求解函数，那么可以得到以下推倒公式：
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2)（n>=3，n∈N*）
用程序实现它：
private static int getFSNum(int n) {
if (n == 1 || n == 2) return 1;
return getFSNum(n-1) + getFSNum(n-2);
}
测试：
System.out.println(getFSNum(1) + "");
System.out.println(getFSNum(2) + "");
System.out.println(getFSNum(3) + "");
System.out.println(getFSNum(4) + "");
System.out.println(getFSNum(5) + "");
输出：
1
1
2
3
5
上面这个求解过程是一个典型递归算法实现，那究竟什么是递归？
递归的概念
递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如回溯、DFS 深度优先搜索等
递归算法的三要素
- 1、一个问题的解可以拆解为一个或多个子问题的解
- 2、这个问题解题思路与拆解后的子问题解题思路完全一致
- 3、必须存在终止条件
只有满足以上三点的解题思路才能使用递归算法。
拿上面斐波那契数列的解题思路来说：
- 1、f(n) 问题可以拆解为 f(n-1)、f(n-2)问题
- 2、无论是f(n)还是子问题f(n-1)、f(n-2)问题，他们的求解思路是一样的
- 3、当n=2或者n==1时，结束“递”，开始“归”
如何判断问题是否适合递归算法
虽然我们知道了递归的三要素，但实际工作中我们很难一眼看出问题是否满足三要素，在这种情况下直接编写递归代码很容易出错，而且为了找到错误，你可能脑子里或者debug形式一步一步去跟踪递归的每一次嵌套调用，相信大多数情况下你还没有摸清出错原因就已经晕了。
其实，就像上面求解斐波那契数列一样，我们尽可能先分析出递推公式，并找到终止条件，最后编写代码。
利用这种思路，试着解下面这个问题：
有n个台阶,每次只能跨1步或者2步，走到第n个台阶有多少种走法？
分析：
n=1 -> 1 -> 1种
n=2 -> 11、2 -> 2种
n=3 -> 111、12、21 -> 3种
n=4 -> 1111、112、121、211、22 -> 5种
假设f(n)为求解函数：
- n=1时，只有1个解；
- n=2时，只有2个解；
- n>2时，分两种情况，这两种情况的总和就是f(n)的解：
- 当第一次走1步时，就需求剩余n-1个台阶的解f(n-1)；
- 当第一次走的是2步时，需求剩余n-2个台阶的解f(n-2)。
得到公式：
f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)（n>2，n∈N*）
有了公式，写代码就简单了：
private static int getStepNum(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return getStepNum(n - 1) + getStepNum(n - 2);
}
测试：
System.out.println(getStepNum(1) + "");
System.out.println(getStepNum(2) + "");
System.out.println(getStepNum(3) + "");
System.out.println(getStepNum(4) + "");
输出：
1
2
3
5
递归算法的堆栈溢出问题
通过上面的两个例子，发现递归算法写出的代码都很清爽简洁，易于理解。
但实际开发中递归算法很容易导致堆栈溢出，从而有很多人都不推荐写递归算法。比如上面的台阶问题，当我改成5000个台阶时，运行在我的编译器上就抛出了StackOverflowError.
System.out.println(getStepNum(5000) + "");
运行，抛出StackOverflowError异常：
Exception in thread "main" java.lang.StackOverflowError
at com.ljb.aljs.Text08.getStepNum(Text08.java:29)
...
这又是为什么？
在“栈的章节-栈的使用场景”有提到函数的调用在内存中是以栈的形式把函数域中的临时变量全部压栈，只有函数调用完毕后才会出栈释放这些资源。而由于递归算法的特殊性，每一次调用都会压入该栈中，层次越深的递归算法所需的栈空间也就越大，然而系统或者JVM虚拟机的函数调用栈一般都不大，从而越深的递归算法越容易堆栈溢出。
如何避免堆栈溢出
1、限制递归深度
顾名思义，从代码层面上增加递归深度的计数器，当达到指定深度直接停止递归（throw Exception）。
显然这种方法不能根本解决问题，只适用于明确规定计算深度的业务场景。
2、优化重复计算
拿上面台阶的例子来说，当要求f(5)=f(4)+f(3)，需要先求f(4)=f(3)+f(2)，可以发现在f(4)中已经计算过f(3)，在f(5)中又要重新计算。
对于递归中这种重复计算的问题，我们可以进行优化,先将已经计算过的解保存起来（例如：散列表），在下次计算时检查是否已经计算过，从而避免重复计算。
优化后的5000个台阶问题，代码如下：
private static int getStepNum(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (cache.containsKey(n)) {
return cache.get(n);
}
int result = getStepNum(n - 1) + getStepNum(n - 2);
cache.put(n, result);
return result;
}
虽然我们优化了重复计算问题，并且可以计算出5000个台阶的结果了，但是这也仅仅是优化，当n足够大时依旧会堆栈溢出。
3、改为循环语句
基本上所有的递归代码都可以改为循环语句。
改写台阶问题：
private static int getStepNum(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int result = 0, pre = 2, prepre = 1;
for (int i = 3; i <= n; i++) {
result = pre + prepre;
prepre = pre;
pre = result;
}
return result;
}
这也是为什么有人提出不要使用递归算法的原因，但我个人认为，在明确知道递归深度不高的情况下优先使用递归，往往使用循环改写后的代码不易于阅读和维护，递归写法的代码阅读性要好很多。
小结
递归算法是一种简洁高效的代码书写方式，只要问题满足三要素都可以使用递归来解决，在无法确定是否满足三要素的情况下，可以先推导出递推公式后再进行编码。
递归算法虽然简洁高效，但也会带来堆栈溢出、重复计算、函数调用耗时、空间复杂度高等弊端。
注：文中提到debug不要一步一步跟进代码，不是指递归不可以进行debug调试，一般情况下调试递归代码有两种方式：1、在递归过程中对特定数据加判断，在此处打断点；2、输出日志，定位错误数据。