Java 中的递归斐波那契数列

Java 9月前 21

斐波那契数列

由从 0 和 1 开始的最后两个数字相加形成的序列。如果要查找第 n 个元素，则可以通过(n-1)和(n-2)项相加来找到该数字，其中 n 必须大于 0。

递归

递归是一个过程，其中相同的确定性函数或过程多次调用其自身，直到遇到终止条件为止。如果不指定终止条件，则该方法将进入无限循环状态。

Java 中的递归斐波那契数列

在下面给出的代码中，main() 方法调用在该类中定义的静态函数 getFibonacciNumberAt()。该函数采用一个定义数字的参数，我们要在其中评估斐波那契数。该函数具有一次主要检查，当它符合所需条件时将返回 0 或 1。否则，该函数将通过减少传递给它的参数来再次调用自身。

package recursiveFibonacci;
public class RecursiveFibonacciSequence {
    public static void main(String[] args) {
        int fibonacciNumber = getFibonacciNumberAt(6);
        System.out.println(fibonacciNumber);
    }
    public static int getFibonacciNumberAt(int n) {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        else
            return getFibonacciNumberAt(n - 1) + getFibonacciNumberAt(n - 2);
    }
}

输出：

详细的评估如下所示：

getFibonacciNumberAt(6) = getFibonacciNumberAt(5) + getFibonacciNumberAt(4); //5+3=8
getFibonacciNumberAt(5) = getFibonacciNumberAt(4) + getFibonacciNumberAt(3); //3+2=5
getFibonacciNumberAt(4) = getFibonacciNumberAt(3) + getFibonacciNumberAt(2); //2+1=3
getFibonacciNumberAt(3) = getFibonacciNumberAt(2) + getFibonacciNumberAt(1); //1+1=2
getFibonacciNumberAt(2) = getFibonacciNumberAt(1) + getFibonacciNumberAt(0); //1+0=1
If, getFibonacciNumberAt(1) = 1;
And getFibonacciNumberAt(0) = 0;

我们可以修改上述程序，以打印出所需数量的序列。

package recursiveFibonacci;
public class RecursiveFibonacci {
    public static void main(String[] args) {
        int maxCount = 10;
        for (int i = 0; i <= maxCount; i++) {
            int fibonacciNumber = printFibonacci(i);
            System.out.print(" " + fibonacciNumber);
        }
    }
    public static int printFibonacci(int n) {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        else
            return printFibonacci(n - 1) + printFibonacci(n - 2);
    }
}