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