P12-斐波那契数列-去重递归/双指针迭代

//斐波那契数列
/*
* 取第N位的值(0开始,8是第6位)，0,1,1,2,3,5,8....
* */
public class P12 {
    public static void main(String[] args) {
        System.out.println(calculate(7));
        System.out.println(calculate2(7));
        System.out.println(iterate(7));
    }

    //1、最常见的是暴力递归
    public static int calculate(int num){
        if(num == 0){
            return 0;
        }
        if(num == 1){
            return 1;
        }

        return calculate(num-1) + calculate(num-2);
    }

    //2、去重递归，时间、空间都是 O(n)
    // 上面的方法要计算calculate(num-1) 和 calculate(num-2)
    // 出现重复计算的问题，例如calculate(9) + calculate(8)，8会在9的分支上计算，所有右侧分支根本没必要计算
    public static int calculate2(int num){
        int[] arr = new int[num+1];
        return recurse(arr, num);
    }
    private static int recurse(int[] arr, int num){
        if(num == 0){
            return 0;
        }
        if(num == 1){
            return 1;
        }

        //num刚好可以作为数组下标
        if(arr[num] != 0){      //代表该下标已经有值，
            return arr[num];    //不需要再递归了
        }
        arr[num] = recurse(arr, num-1) + recurse(arr, num-2);
        return arr[num];
    }

    //3、双指针算法
    // 上方的方法是用数组存起每个值，但这些值用完之后就没用的了
    // 只需要3个空间，两个指针+一个sum，每次计算完都赋值为下一个数
    /*
    * 0 1 1 2 3 5 8
    * ↑ ↑ s
    *   ↑ ↑ s
    * */
    private static int iterate(int num){
        if(num == 0){
            return 0;
        }
        if(num == 1){
            return 1;
        }

        int low = 0;
        int high = 1;
        for(int i=2; i<=num; i++){
            int sum = low+high;
            low = high;
            high = sum;
        }

        return high;
    }
}