Java斐波那契数列

斐波那契数列又称黄金分割数列，从第三个数开始，每一个数是前两个数的和。
例：0，1，1，2，3，5，8，13...

三种方法实现斐波那契数列

    //(1)递归：函数自己调用自己
    //(2)递归的"缺陷"：递归到一定程度，会发生"栈溢出"
    //(3)递归的"时间复杂度"：递归总次数*每次递归的次数
    //递归的"深度"：树的高度（递归的过程是一个"二叉树"）
    private static int Fib1(int n) {
        //从第三个数开始，最后一个数是前两个数的和 Fn = F(n-1) + F(n-2)
        if (n <= 2) {
            return 1;
        }

        return Fib1(n - 1) + Fib1(n - 2);
    }

    //循环实现斐波那契数列
    //时间复杂度：O(N)
    //空间复杂度：O(1)
    //此种方法是"最优方法"
    //优点：时间复杂度和空间复杂度最低
    private static long Fib2(long N) {
        long first = 1;
        long second = 1;
        long ret;
        for (int i = 3; i <= N; ++i) {
            ret = first + second;
            first = second;
            second = ret;
        }
        return second;
    }

    //数组形式打印
    private static void Fib3(int n) {
        int[] arr = new int[n];
        arr[1] = 1;
        arr[2] = 1;
        System.out.println(arr[1]);
        System.out.println(arr[2]);
        for (int i = 3; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            System.out.println(arr[i]);
        }
    }