一、递归的定义

1.递归是一个非常重要的算法思想

应用也是相当的广泛，包括我们后面学的数据结构尤其是树形结构里面跟递归是密不可分的。所以大家是一定要学懂它的，其实递归说起来很简单，生活中也是经常可以碰到这个场景，
比如我们在某窗口排队人太多了，我不知道我排在第几个，那么我就问我前面的人排第几个，
因为知道他排第几我就知道我是第几了。但前面的人也不知道自己排第几那怎么办呢？他也可以继续往前面问，直到问到第一个人，然后从第一个人一直传到我这里 我就很清楚的知道我是第几了。以上这个场景就是一个典型的递归。我们在这个过程中大家有没有发现一个规律那么就是会有一个问的过程，问到第一个后有一个回来的过程吧。这就是递（问）加归（回），回来的这个过程也叫回朔。那么这个过程我们是不是可以用一个数学公式来求解呢？那这个数学公式又是什么？
f(n)=f(n-1)+1
f(n):表示我的位置
f(n-1):表示我前面的那个人；
自己调用自己；

2.什么样的情况下可以用递归？

（1）一个问题的解可以分解为几个子问题的解：子问题，我们通过分治的思想可以把一个数据规模大的问题，分解为很多小的问题。
我们可以把刚刚那个问前面的那个人看为子问题。大化小
（2）这个问题与分解之后的子问题，求解思路完全一样：
（3）一定有一个最后确定的答案，即递归的终止条件：刚刚那个问题就是第一个人。第一个人是肯定知道自己排第几吧即n=1的时候，如果没有这个特性那么我们这个递归就会出现死循环，最后程序就是栈溢出；stack out of

3.递归实现斐波那契数列：

1 1 2 3 5 8 13 21
斐波那契数列有什么特点？
从第三个数开始 就等于前面两个数相加

public static void main(String[] args) {
        data = new int[101];
        for(int i=1;i<=6;i++){
            long startTime = System.currentTimeMillis();
            System.out.println(i+":"+fabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            //System.out.println(i+":"+noFabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            //System.out.println(i+":"+fabSub2(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
        }
    }

运行结果：

下图对上面的逻辑代码进行一个分析：

从上图就可以看出，当数值较大时，如输入的数字不是6而是50时就要十多秒了，对于这样的递归效率显然是不能接受的，这样递归的效率非常低，递归中有大量重复的运算，那我们要怎样做优化呢

二、递归优化

1.利用循环进行优化

用普通循环做优化

//1 1 2 3 5 8 13 21
    public static int noFabSub(int value){
        if(value<=2) {
            return 1;
        }
        else{
            int f1 = 1;
            int f2 = 1;
            int sum = 0;
            for(int i =3;i<=value;i++){
                sum = f1+f2;
                f1 = f2;
                f2 = sum;
            }
            return sum;
        }
    }

public static void main(String[] args) {
        data = new int[10151];
        for(int i=1;i<=100;i++){
            long startTime = System.currentTimeMillis();
            //System.out.println(i+":"+fabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            System.out.println(i+":"+noFabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            //System.out.println(i+":"+fabSub2(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
        }
    }

2.利用缓存进行优化

缓存优化（将相同的计算结果用缓存存起来，直接复用）

//1 1 2 3 5 8 13 21
    public static int noFabSub(int value){
        if(value<=2) {
            return 1;
        }
        else{
            int f1 = 1;
            int f2 = 1;
            int sum = 0;
            for(int i =3;i<=value;i++){
                sum = f1+f2;
                f1 = f2;
                f2 = sum;
            }
            return sum;
        }
    }

private static int data[];
public static void main(String[] args) {
        data = new int[101];
        for(int i=1;i<=100;i++){
            long startTime = System.currentTimeMillis();
            //System.out.println(i+":"+fabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            //System.out.println(i+":"+noFabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            System.out.println(i+":"+fabSub2(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
        }
    }

3.尾递归进行优化

什么是尾递归？尾递归就是调用函数一定出现在末尾，没有任何其他的操作了。因为我们编译器在编译代码时，如果发现函数末尾已经没有操作了，这时候就不会创建新的栈，而且覆盖到前面去。
倒着算，不需要在回溯了，因为我们每次会把中间结果带下去。

//1 1 2 3 5 8 13 21
    public static int tailFab(int n,int res, int pre){
        if(n<=2) {
            return res;
        }
        return tailFab(n -1 ,res + pre,res);
    }

public static void main(String[] args) {
        data = new int[101];
        for(int i=1;i<=60;i++){
            long startTime = System.currentTimeMillis();
            //System.out.println(i+":"+fabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            //System.out.println(i+":"+noFabSub(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            //System.out.println(i+":"+fabSub2(i)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
            System.out.println(i+":"+tailFab(i,1,1)+"用时:"+ (System.currentTimeMillis()-startTime) + "ms");
        }
    }

三、分治

分治的思想可以把一个数据规模大的问题，分解为很多小的问题。
我们可以把刚刚那个问前面的那个人看为子问题。大化小

四、数论思想

数论思想：利用数学公式或者定理或者规律求解问题；