Java 中的遞迴斐波那契數列
Rashmi Patidar
2023年1月30日
2021年4月29日
斐波那契數列
由從 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 類。對於較大的數字，遞迴過程將很複雜；因此，此類數字的計算時間也將更長。Author: Rashmi Patidar
Rashmi is a professional Software Developer with hands on over varied tech stack. She has been working on Java, Springboot, Microservices, Typescript, MySQL, Graphql and more. She loves to spread knowledge via her writings. She is keen taking up new things and adopt in her career.
LinkedIn