递归之斐波那契数列Java的3种方法

什么是斐波那契数列

在数学中，斐波那契数列是以递归的方式定义的：前两个数字是0和1，随后每个数字都是前两个数字的和。

斐波那契数列的前几个数字是0、1、1、2、3、5、8、13、21、34……以此类推。

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

方法1：最基本的递归方法

这是最基本的递归方法，但是由于重复计算太多，不适合大规模的计算，速度很慢。

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

方法2：加入缓存的递归方法

我们可以使用一个数组来存储每个子问题的解，避免了重复计算。这种方法被称为“记忆化搜索”或“自顶向下的动态规划”，速度较上一个方法提高了很多。

public static int fib2(int n) {
    int[] cache = new int[n + 1];
    return fib2Helper(cache, n);
}

private static int fib2Helper(int[] cache, int n) {
    if (n <= 1) {
        return n;
    } else if (cache[n] != 0) {
        return cache[n];
    } else {
        int result = fib2Helper(cache, n - 1) + fib2Helper(cache, n - 2);
        cache[n] = result;
        return result;
    }
}

方法3：非递归方法

我们也可以使用非递归方法来计算斐波那契数列。这个方法使用了一个数组来存储每个子问题的解，避免了重复计算。这种方法被称为“自底向上的动态规划”，速度是最快的。

public static int fib3(int n) {
    int[] fib = new int[n + 1];
    fib[0] = 0;
    if (n > 0) {
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
    return fib[n];
}

示例说明

示例1

我们要求斐波那契数列的第10项，可以调用方法1：

int result = fib1(10);
System.out.println(result);

输出为55。

示例2

我们要求斐波那契数列的第20项，可以调用方法3：

int result = fib3(20);
System.out.println(result);

输出为6765。