java实现斐波那契数列的3种方法

以下是详细讲解“Java实现斐波那契数列的3种方法”的完整攻略。

一、斐波那契数列简介

斐波那契数列（Fibonacci Sequence）是一个非常经典的数学问题，它的定义如下：

斐波那契数列是一列数字，第一和第二项为 1，之后的每一项都是前两项之和。

数列的前几项为：1,1,2,3,5,8,13,21,34,55,89,144,… …

二、Java实现斐波那契数列的3种方法

1. 递归实现

递归实现是最为直观的一种方法，其代码如下：

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

上述代码中，我们使用了递归的方式，当 n<=1 时直接返回 n，当 n>1 时则返回 fibonacciRecursive(n-1) + fibonacciRecursive(n-2) 的值。需要注意的一点是，这种方法会造成时间复杂度的极大增加，因为会存在重复计算。

2. 迭代实现

迭代实现是一种比递归实现更加高效的方法。其代码如下：

public static int fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    int first = 1;
    int second = 1;
    int result = first + second;
    for (int i = 3; i <= n; i++) {
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

上述代码中，我们使用了 for 循环，依次计算每一项的值，并将其累积到结果中。需要注意的是，为了便于计算，我们对第一项和第二项进行了初始化。

3. 动态规划实现

动态规划实现是一种比迭代实现更加高效的方法，其代码如下：

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

上述代码中，我们使用了动态规划的方式，将每一项的值暂存在数组 arr 中，便于后续的累积计算。需要注意的一点是，这种方法虽然空间复杂度比较高，但是时间复杂度较低，并且避免了重复计算。

三、示例说明

以下是两条对斐波那契数列的计算示例说明：

示例 1

输入：n = 5

输出：5

解释：斐波那契数列的前五项为[1, 1, 2, 3, 5]，第五项即为 5。

计算过程：

i	1	2	3	4	5
arr[i]	1	1	2	3	5

示例 2

输入：n = 8

输出：34

解释：斐波那契数列的前八项为[1, 1, 2, 3, 5, 8, 13, 21, 34]，第八项即为 34。