JAVA递归与非递归实现斐波那契数列

本文将详细讲解“JAVA递归与非递归实现斐波那契数列”的完整攻略，包括什么是斐波那契数列，递归实现方式及非递归实现方式等内容。

什么是斐波那契数列

斐波那契数列是一个无限长的整数序列，其前两项为0和1，后续项均为前两项之和。其数列如下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

递归实现方式

递归是一种简单而又常见的算法实现方式，斐波那契数列也可以使用递归的方式来实现。代码如下：

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

该方法的实现方式是基于定义斐波那契数列的数学递推公式，在该方法中我们不断调用自身来计算前两项之和，直到达到指定的项数为止。但这种方法在计算大量项数时，时间复杂度非常高，容易造成堆栈溢出或者超时的情况。

非递归实现方式

斐波那契数列也可以使用非递归的方式来实现，其主要思路是使用循环来迭代计算每一项的值，代码如下：

public static long fibonacciNonRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    long fibNMinusTwo = 0;
    long fibNMinusOne = 1;
    long fibN = 1;
    for (int i = 2; i <= n; i++) {
        fibN = fibNMinusOne + fibNMinusTwo;
        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }
    return fibN;
}

这种实现方式不会像递归方法一样造成堆栈溢出问题，计算速度也较快，是一种实际上更可取的方法。

示例说明

下面给出两个使用Java递归和非递归方式实现斐波那契数列的示例代码：

import java.io.*;

public class Fibonacci {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("请输入要计算的斐波那契数列的项数：");
        int n = Integer.parseInt(br.readLine());
        System.out.println("递归方式计算斐波那契数列第" + n + "项的值为：" + fibonacciRecursive(n));
        System.out.println("非递归方式计算斐波那契数列第" + n + "项的值为：" + fibonacciNonRecursive(n));
    }

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

    public static long fibonacciNonRecursive(int n) {
        if (n <= 1) {
            return n;
        }
        long fibNMinusTwo = 0;
        long fibNMinusOne = 1;
        long fibN = 1;
        for (int i = 2; i <= n; i++) {
            fibN = fibNMinusOne + fibNMinusTwo;
            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne = fibN;
        }
        return fibN;
    }
}

在这个例子中，用户通过输入要计算的项数，程序会分别使用递归和非递归方式计算结果，并输出到控制台。

总结

本文介绍了斐波那契数列的定义及其用递归和非递归方式实现的方法，尤其是非递归方式实现的方法可以避免递归在计算过程中造成的堆栈溢出问题，效率更高。