算法—递归及尾递归
- 2020 年 4 月 9 日
- 筆記
什么叫递归？举个例子，我们排队，想知道自己排在第几个，那么我们可以问前面的那个人，前面的人继续问前面，直到问到第一个人，这就是传递的过程。然后再从第一个人回来，这就是归（回溯）的过程。传递过去再回归回来，这就是递归。第一个人就是我们所说的递归出口，也就是说到哪个点应该回归了，如果没有出口，那么就会死循环了栈溢出。
在代码中简单来说就是自己调用自己。拿到自己的结果再作为入参调用自己。
比如我们求阶乘：
5的阶乘： 5*4*3*2*1
我们用递归来写，那么出口就是n=1的时候：代码如下
/** * 阶乘 * @param n * @return */ public static int factorial(int n) { if (n <= 1) { return 1; } return n * factorial(n - 1); }
调用过程如下:
走到1的时候最后再一次回来计算结果，最后返回。这就是递归。
再来看一个比较经典的例子，裴波那契数列，1,1,2,3,5,8,13,21….后一项永远是前两项之和，
用递归来实现：
/** * 裴波那契数列 递归 * @param n * @return */ public static int recursion(int n) { if (n <= 2) { return n == 0 ? 0 : 1; } return recursion(n - 1) + recursion(n - 2); }
是不是感觉递归写起来代码很少。看起来也干净。但是当执行上面裴波那契数列的代码，比如设置一个45，你会发现很久都计算不出来，为什么呢？
递归一个递和一个归的过程无疑是增加了时间复杂度的，阶乘那个的时间复杂度还好O（2n）也就是O（n），但是裴波那契数列就是O（2^n），因为每个值进去都有两个分支，就像1生2,2生4,4生8这种了，所以是2^n。就像这样：
从这个图里面还看出来几乎所有的值都会被多次计算，在每一个分支都去计算多次。
所以我们需要来优化我们上面的代码：
1.非递归实现，按理来说，每一个递归都可以用非递归来实现
裴波那契数列非递归实现，时间复杂度O（n）
/** * 裴波那契数列循环实现 * @param n * @return */ public static int cycle(int n) { if (n <= 2) { return n <= 0 ? 0 : 1; } int f1 = 1; //n-1 int f2 = 1; //n-2 int fn = 0; // n for (int i =3; i<=n;i++) { fn = f1 + f2; f2 = f1; f1 = fn ; } return fn ; }
2.保存中间结果，刚才也说到了，裴波那契数列那个递归的实现，会让很多值多次计算，声明一个数组做缓存，把中间结果放入数组中存起来，计算的时候先去数组中取，如果有就不计算了
public static int cache(int n) { int data[] = new int[n]; // 用数组来做缓存 return fac(n, data); } public static int fac(int n, int[] data) { if (n <= 2) return 1; //递归的终止条件 if (data[n-1] > 0) { //数组中有值就直接取出来返回，不用再去计算 return data[n-1]; } int res = fac(n - 1, data) + fac(n - 2, data); data[n-1] = res; //算出来值放到数组中 return res; }
3.尾递归。为什么有些递归会栈溢出，因为每个方法调用都会创建新的栈。如果没有控制好递归的深度，肯定是会栈溢出的。
尾递归就是，函数调用在末尾，且末尾只能有函数调用，不能有其他操作。这样编译器在编译代码的时候如果发现末尾只有函数调用，不会创建新的栈。也就说最后我们的方法返回就是返回的我们的最终结果。如何才能做到这样呢，其实就需要将前面的计算结果传递到最后，递归出口即是结束，没有回溯的过程。
阶乘的尾递归实现：
/** * 阶乘尾递归 * @param n * @return */ public static int taiFactorial(int n, int result) { if (n <= 1) { return result; //最后返回的即是最终结果 } return taiFactorial(n - 1, n * result);//结果往下传 }
裴波那契数列尾递归：
/** * 尾递归 裴波那契 * @param pre 上上一次运算出来的结果 * @param result 上一次运算出来结果 * @param n * @return */ public static int tailRecursion(int pre, int result, int n) { if (n <= 2) { return result; } //对于下一次调用来说 前一次结果 pre + result 前前一次result return tailRecursion(result, pre + result, n - 1); }
测试下裴波那契数列普通递归和尾递归执行效率：
public static void main(String[] args){ System.out.println("---裴波那契数列普通递归---"); long time1 = System.currentTimeMillis(); int result = recursion(45); System.out.println(result); long time2 = System.currentTimeMillis(); System.out.println(time2-time1); System.out.println("---裴波那契数列尾递归---"); result = tailRecursion(1,1,45); System.out.println(result); long time3 = System.currentTimeMillis(); System.out.println(time3-time2); }
所以我们对于递归的使用一定要慎重！！！
