Java 中的递归斐波那契数列

  1. 斐波那契数列
  2. 递归
  3. Java 中的递归斐波那契数列

斐波那契数列

由从 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);
    }
}

输出:

8

详细的评估如下所示:

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);
    }
}

输出:

0 1 1 2 3 5 8 13 21 34 55
注意

为了计算更大的数字,我们可以使用 Java 中的 BigInteger 类。对于较大的数字,递归过程将很复杂;因此,此类数字的计算时间也将更长。

相关文章 - Java Math

  • 在 Java 中生成指定范围内的随机数