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