递归

递归简单的理解就是自己调用自己，注意递归的条件，否则会造成一直递归，栈溢出.

用递归的方式来算出斐波那契数列的值

 public static int fib(int n){
        if(n <= 2) return 1;
        return fib(n-2) + fib(n-1);
    }

这种方法有很大的缺点，会重复调用函数.比如求fib（5），把它分成fib（4）+ fib（3），fib（4）又会分成fib（3）+fib（2）。这样就会重复调用两次fib（3）；

改进的方式

 

 public static int fib1(int n){
        if(n <= 2 ) return 1;
        int[] array = new int[n+1];
        array[1] = 1;
        array[2] = 1;
        return fib1(n,array);
    }

    public static int fib1(int n , int[] array){
        if(array[n] == 0){
            array[n] = fib1(n-1,array)+fib1(n-2,array);
        }
        return array[n];
    }

通过用数组来记录值的方式，就可以避免重复调用，只要数组里有值，就不需要在递归求值，直接返回数组里面的值就可.

采取非递归的方式

 public static int fib2(int n){
        int[] array = new int[n+1];
        array[1] = array[2] = 1;
        for (int i = 3 ; i <= n ; i++){
            array[i] = array[i-1] + array[i-2];
        }
        return array[n];
    }

 public static int fib3(int n){
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3 ; i <= n ; i++){
            array[i & 1] = array[(i-1) & 1] +array[(i-2) & 1];
        }
        return array[n & 1];
    }

此方法只需要数组长度为2即可，重复利用.

 public static int fib4(int n){
        int first  = 1;
        int second = 1;
        for(int i = 3 ; i <= n ; i++){
            second = first + second;
            first = second - first;
        }
        return second;
    }

直接利用两个变量来存取值、