斐波那契数列的三种解法

斐波那契数列
求取斐波那契数列第N位的值。
斐波那契数列：前两位数字是固定的0和1，后面每一位的值等于他前两位数字之和。0,1,1,2,3,5,8……
解法一：暴力递归
从下图中可以看到，暴力递归充斥着大量的重复数字，也就进行了大量的重复计算。

解法二：去重递归
递归得出某一个具体数值之后，先存储到一个集合(下标与数列下标一致)，后面数字递归之前先到这个集合查询，如果能够查到就直接取值，不需要递归，查不到再进行递归计算。从下图看，我们只需要计算最左侧一边的数字即可，其他数字可以直接从集合中取。

解法三：双指针迭代
基于去重递归优化，集合没有必要保存每一个下标值，只需保存前两位即可，向后遍历，得出N的值。

package od;

/**
 * 斐波那契数列（3种解法）
 * 求取斐波那契数列第N位的值。
 * 斐波那契数列：前两位数字是固定的0和1，后面每一位的值等于他前两位数字之和：0,1,1,2,3,5,8……
 * 原文地址：https://www.codernav.com/2831.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest26 {
    public static void main(String[] args) {
        // 解法一：暴力递归
        System.out.println(f1(10));
        // 解法二：去重递归(此处用数组存储，也可以用Map)
        int[] arr = new int[10 + 1];
        System.out.println(f2(arr, 10));
        // 解法三：双指针.迭代
        System.out.println(f3(10));
    }

    public static int f1(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        return f1(num - 1) + f1(num - 2);
    }

    public static int f2(int[] arr, int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        if (arr[num] != 0) {
            return arr[num];
        }
        arr[num] = f2(arr, num - 1) + f2(arr, num - 2);
        return arr[num];
    }

    public static int f3(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        int low = 0, high = 1;
        for (int i = 2; i <= num; i++) {
            int sum = low + high;
            low = high;
            high = sum;
        }
        return high;
    }


}