文章结构
- 递归是什么
- 递归需要满足的三个条件
- 如何编写递归代码
- 递归代码要警惕堆栈溢出
- 递归代码要警惕重复计算
- 怎样将递归写成非递归代码
1. 递归是什么
递归简单的理解就是，函数自己调用自己。我们看一个计算阶乘的函数
//n!=n*(n-1)*(n-2)……*2*1
private static int fun(int n) {
if (n <= 0) {//递归结束条件
return 1;
}
return n * fun(n - 1);//问题拆分，递归公式
}
函数fun()就在它自己的方法体里面再次调用了fun()。
递归的应用非常广泛，在很多的数据结构和算法中都需要用到。比如说：DFS深度优先搜索、二叉树的遍历等等
2. 递归需要满足的三个条件
什么样的问题适合使用递归来解决呢？归纳起来有如下三条
- 一个问题的解可以分解为几个子问题的解
如求解n的阶乘，可以分解成n*(n-1)的递归
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
n-1的递归和n的递归的解决思路是完全一致的，只是数据规模不一样
- 存在递归终止条件
当n==1的时候，1的阶乘就是1；如果没有终止条件，递归将无限循环直到内存溢出
3. 如何编写递归代码
编写递归代码的关键就是找到如何将大问题分解成小问题的规律，并且基于此写成递推公式，并且推敲出终止条件，然后将递推公式和终止条件翻译成代码。
举例说明
假如有n个台阶，每次你可以跨1个台阶或者2个台阶。请问走这n个台阶总共有多少种走法
找到如何将大问题分解成小问题的规律
我们倒过来从最后一步的走法开始分析，每次可以跨1个台阶或者2个台阶，所以当走最后一步的时候，所在的台阶就是（n-1或者n-2）。那么n阶台阶的走法数量就是走到第n-1级台阶的走法数量加上走到第n-2级台阶的走法数量之和。用公式表示就是：f(n)=f(n-1)+f(n-2)。
这样我们就找到了递推公式。然后我们在来推导终止条件
推导终止条件
- 当只有一步阶梯的时候，我们只有1种走法：f(1)=1;
- 当有两步阶梯的时候，我们有一次走一步，走两次和一次走两步，走一次两种走法：f(2)=2;
有了递推公式和终止条件，我们将递推公式翻译成代码
将递推公式翻译成代码
public int fun(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return fun(n - 1) + fun(n - 2);
}
4. 递归代码要警惕堆栈溢出
递归代码如何没有终止条件，将无限递归，这样最后就会出现内存溢出问题。如我们注释掉上面的两个终止条件，则代码会报异常
public int fun(int n) {
// if (n == 1) {
// return 1;
// }
// if (n == 2) {
// return 2;
// }
return fun(n - 1) + fun(n - 2);
}
运行异常：
java.lang.StackOverflowError
at com.hym.datastructure.recursion.WalkStairs.fun(WalkStairs.java:24)
at com.hym.datastructure.recursion.WalkStairs.fun(WalkStairs.java:24)
5. 递归代码要警惕重复计算
像上面f(n)=f(n-1)+f(n-2)的递推公式，我们用递归树来分析一下它的计算过程
我们会发现：计算f(5)，需要先计算f(4)和f(3),而计算f(4)还需计算f(3),因此，f(3)就被计算了两次。我们可以采用缓存中间的计算结果来优化计算速度。我们将上面的代码优化成这样,使用arrays数组来缓存中间的计算结果，如果已经计算过了，则不再重复去计算
/**
* 过滤重复计算的方式
*
* @param n
* @return
*/
public int fun2(int n) {
int[] arrays = new int[n + 1];
return fun(arrays, n);
}
private int fun(int[] arrays, int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int count1 = arrays[n - 1] > 0 ? arrays[n - 1] : fun(arrays, n - 1);
int count2 = arrays[n - 2] > 0 ? arrays[n - 2] : fun(arrays, n - 2);
int count = count1 + count2;
arrays[n] = count;
return count;
}
看一下两种方式的对比效果，执行如下测试代码
@Test
public void compare() {
int n = 40;//对比分析两种计算方式消耗的时间
long start1 = System.currentTimeMillis();
System.out.println("fun:" + fun(n));
System.out.println("fun time:" + (System.currentTimeMillis() - start1));
long start2 = System.currentTimeMillis();
System.out.println("fun2:" + fun2(n));
System.out.println("fun2 time:" + (System.currentTimeMillis() - start2));
}
运行结果
fun:165580141
fun time:329
fun2:165580141
fun2 time:0
我们看到第二种方式消耗的时间比第一种方式要少很多，第二种几乎为0，而第一种随着数据规模的增大，消耗将更大。但是fun2这种方式虽然计算时间少了，不过它额外的申请了一个保存中间状态的数组array，它的空间复杂度为O(n)。这里反映出一个总要的算法思想算法设计很多时间就是在时间复杂度和空间复杂度之间追求一个平衡：多用点空间，就能提升点时间；而少用点空间，就可能多花点时间
这个例子的完整实例代码，可前往github之WalkStairs
6. 怎样将递归写成非递归代码
递归有利有弊，利是递归代码的表达力强，写起来非常简洁；而弊就是空间复杂度高，有堆栈溢出的风险，存在重复计算等问题。
我们将上面的上楼梯走法求解算法改成非递归写法
/**
* 非递归写法
*
* @param n
* @return
*/
public int fun3(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i <= n; i++) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
说明
文中图片来源：极客时间，王争《数据结构与算法之美》
