Java函数实现求解斐波那契数列的递归与非递归算法

斐波那契数列是一个非常经典的数学问题，它是一个递归定义的数列，以递推公式 F(n) = F(n-1) + F(n-2) 而闻名。

首先，我们来看一下如何使用递归算法来求解斐波那契数列。

递归算法是一种将大问题分解为小问题的解决方法。求解斐波那契数列可以通过将问题分解为求解前两个数的和的问题来实现。具体的递归算法如下：

public static int fibonacci(int n) {
    // 终止条件
    if (n <= 1) {
        return n;
    }

    // 递归调用
    return fibonacci(n-1) + fibonacci(n-2);
}

在递归算法中，我们首先判断终止条件，当 n 小于等于 1 时，就直接返回 n。然后，我们通过递归调用 fibonacci(n-1) + fibonacci(n-2) 来求解斐波那契数列的第 n 个数。

然而，递归算法在求解斐波那契数列时存在一些问题。它的时间复杂度为 O(2^n)，即指数级别的复杂度，在 n 的值较大时会非常耗时。因此，我们可以使用非递归的方式来改进算法，提高求解效率。

非递归算法是一种通过循环遍历的方式来求解问题的算法。对于斐波那契数列，我们可以通过动态规划的方式来实现非递归算法。

具体的非递归算法如下：

public static int fibonacci(int n) {
    // 创建一个数组，用来保存斐波那契数列的前两个数
    int[] fib = new int[n+1];

    // 初始化斐波那契数列的前两个数
    fib[0] = 0;
    fib[1] = 1;

    // 通过循环遍历求解斐波那契数列的第 n 个数
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }

    return fib[n];
}

在非递归算法中，我们首先创建一个数组 fib 来保存斐波那契数列的前两个数。然后，我们通过一个循环遍历，计算出斐波那契数列的第 n 个数，并保存在数组 fib 中。最后，返回斐波那契数列的第 n 个数。

非递归算法的时间复杂度为 O(n)，相比递归算法来说，具有明显的优势。在实际应用中，我们应该尽量避免使用递归算法，而选择非递归算法来求解斐波那契数列。