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