1.递归的概念

算法中比较难的是递归和动态规划（比较难）。

递归的实际生活场景：
比如我在排队，前面排了很多人，所以我就问前面的一个人，前面的人再问前面的人，一直问到第一个人，然后第二个人就知道自己排第二个，传到我自己我就知道自己到底排到多少人了。问的过程就是递，回来的就是归。
这个排队的递归过程用数学的公式就是
f(n)=f(n-1)+1

f(n):就是我排到第几个人。
f(n-1)：就是前一个人排到的位置。

递归就是自己调用自己。

image.png

2.递归使用场景

1.大的问题分解成多个子问题
2.子问题求解的方式是一样的
3.递归的终止条件

3.实战

  1. //1 1 2 3 5
  2.     public static int floba(int n) {
  3.         if (n <= 2) {
  4.             return 1;
  5.         }
  7.         return floba(n - 1) + floba(n - 2);
  8.     }
  11.     //1 1 2 3 5 8
  12.     //非递归的接发
  13.     public static int floba3(int n) {
  14.         if (n <= 2) {
  15.             return 1;
  16.         }
  18.         int[] data = new int[n + 1];
  19.         data[1] = 1;
  20.         data[2] = 1;
  22.         for (int i = 3; i <= n; i++) {
  23.             data[i] = data[i - 1] + data[i - 2];
  24.         }
  25.         return data[n];
  27.     }
  29.     public static int floba2(int n) {
  30.         int a = 1;
  31.         int b = 1;
  32.         int c = 0;
  33.         for (int i = 3; i <= n; i++) {
  34.             c = a + b;
  35.             a = b;
  36.             b = c;
  37.         }
  38.         return c;
  41.     }

尾递归

尾递归就是将数值传递过下一个方法，这样方法栈都是会被回收的。

递归优化：
(1)使用非递归。所有的递归代码理论上是一定可以转换成非递归的。
(2)加入缓存：把我们中间的运算结果保存起来，这样就可以把递归降至为o(n)
(3)尾递归：什么是尾递归？尾递归就是调用函数一定出现在末尾，没有任何其他的操作了。因为我们编译器在编译代码时，如果发现函数末尾已经没有操作了，这时候就不会创建新的栈，而且覆盖到前面去。倒着算，不需要在回溯了，因为我们每次会把中间结果带下去。

斐波那契数列：

  1.  public static int tailfab(int pre,int res,int n) { // 分析一段代码好坏，有两个指标，时间复杂度和空间复杂度 都是： O(n)
  2.         if (n <= 2)
  3.             return res; // 递归的终止条件
  4.         return tailfab(res, pre + res, n - 1);        //JDK源码
  5.         //参数：
  6.         /**
  7.          * n 是肯定有的
  8.          * res 上一次运算出来结果
  9.          * pre 上上一次运算出来的结果
  10.          */
  11.     }
  1.   //n阶乘的尾递归实现
  2.     public static int factorial2(int n, int res) {
  3.         if (n <= 1) return res;
  4.         return factorial2(n - 1, n * res);
  6.     }