HOWTO · Java
Java 中的遞迴斐波那契數列
本文介紹了在 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 類。對於較大的數字，遞迴過程將很複雜；因此，此類數字的計算時間也將更長。