斐波那契数列 Java 使用递归和循环

斐波那契数列是什么 Java?

A 斐波那契系列 in Java 斐波那契数列是一个数字序列，其中下一个数字是前两个数字之和。斐波那契数列的前两个数字是0和1。斐波那契数列在计算两个整数最大公约数的算法的运行时间研究中得到了广泛应用。

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

用公式表示，该规则为 F(n) = F(n-1) + F(n-2)，其中 F(0) = 0 且 F(1) = 1。下表显示了前八项是如何生成的。

斐波那契数列程序 Java 使用 For 循环

迭代版本在任何时刻都只在内存中保留两个值，这就是为什么它的运行时间为线性时间、空间占用为常数。

//Using  For Loop
public class FibonacciExample {
	public static void main(String[] args)
	{
		// Set it to the number of elements you want in the Fibonacci Series
		 int maxNumber = 10;
		 int previousNumber = 0;
		 int nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */


	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
	}
}

输出：

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

程序逻辑：

• previousNumber 初始化为 0，nextNumber 初始化为 1。
• 斐波那契循环遍历 maxNumber:
  • 显示上一个数字。
  • 计算前一个数字和下一个数字之和。
  • 更新 previousNumber 和 nextNumber 的新值。

斐波那契数列程序 Java 使用 While 循环

您还可以生成一个 Java 使用斐波那契数列 while 循环 Java运算过程完全相同，只有循环语法有所改变。

//Using  While Loop
public class FibonacciWhileExample {
	public static void main(String[] args)
	{
		 int maxNumber = 10, previousNumber = 0, nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");

	        int i=1;
	        while(i <= maxNumber)
	        {
	            System.out.print(previousNumber+" ");
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	            i++;
	        }

	}

}

输出：

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

程序逻辑的唯一区别在于使用了 while 循环来打印斐波那契数列。计数器必须在循环之前声明，并在循环内部递增，否则循环将永远不会结束。

根据用户输入的斐波那契数列

将词项计数硬编码到代码中便于演示，但实际练习通常会从键盘读取该值。Scanner 类只需三行代码即可完成此操作，生成逻辑保持不变。

//fibonacci series based on the user input
import java.util.Scanner;

public class FibonacciUserInput {

    public static void main(String[] args)
    {
        int maxNumber = 0;
        int previousNumber = 0;
        int nextNumber = 1;

        System.out.println("How many numbers you want in Fibonacci:");
        Scanner scanner = new Scanner(System.in);
        maxNumber = scanner.nextInt();
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");

        for (int i = 1; i <= maxNumber; ++i)
        {
            System.out.print(previousNumber + " ");
            /* On each iteration, we are assigning the second number
             * to the first number and assigning the sum of the last two
             * numbers to the second number
             */

            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
        }

        scanner.close();
    }
}

示例运行：

How many numbers you want in Fibonacci:
7
Fibonacci Series of 7 numbers:0 1 1 2 3 5 8

程序逻辑：
逻辑与之前相同。不再硬编码要显示的元素数量， Java 斐波那契数列，要求用户输入一个数字。

斐波那契数列使用递归 Java

下面是一个斐波那契数列程序 Java 使用递归：

//Using Recursion
public class FibonacciCalc{
	public static int fibonacciRecursion(int n){
	if(n == 0){
		return 0;
	}
	if(n == 1 || n == 2){
			return 1;
		}
	return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
	}
    public static void main(String args[]) {
	int maxNumber = 10;
	System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
	for(int i = 0; i < maxNumber; i++){
			System.out.print(fibonacciRecursion(i) +" ");
		}
	}
}

输出：

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

程序逻辑：

递归函数是具有调用自身的能力的函数。

fibonacciRecursion（）：

1. 此 Java 斐波那契递归函数接受一个输入数字。它会检查该数字是否为 0、1 或 2，并分别返回 0、1 或 1，因为斐波那契数列是 2 到 3 的整数。 Java 以 0, 1, 1 开始。
2. 当输入 n 大于等于 3 时，该函数会递归调用自身。调用次数为两次。 trac下面 e 表示需要输入 4。

fibonacciRecursion(4)
    = fibonacciRecursion(2) + fibonacciRecursion(3)

    fibonacciRecursion(2) = 1                    // base case, no further calls
    fibonacciRecursion(3) = fibonacciRecursion(1) + fibonacciRecursion(2)
                          = 1 + 1
                          = 2

    Result: 1 + 2 = 3

基本情况会阻止递归。因为 1 和 2 都立即返回，所以 fibonacciRecursion(2) 的分支永远不会进一步扩展，这正是保持递归的原因。 trac有限的。

利用记忆化优化斐波那契数列

普通的递归会多次重复计算相同的项。计算第 40 项需要超过 200 亿次的调用。而将每次计算的结果在第一次计算时就存储起来，则可以完全消除这种重复计算。

public class FibonacciMemo {

    static long[] cache;

    public static long fib(int n) {
        if (n <= 1) {
            return n;
        }
        // return the stored value when it exists
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }

    public static void main(String[] args) {
        int maxNumber = 90;
        cache = new long[maxNumber + 1];

        System.out.println("Term 50 is: " + fib(50));
        System.out.println("Term 90 is: " + fib(90));
    }
}

输出：

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

斐波那契数列方法的比较 Java

四个程序都打印出相同的序列，因此决定取决于需要多少项。

相同的计数器和累加器模式出现在几个相关的练习中。继续进行。 Java 回文程序， Java 检查质数的程序，并 编写一个程序，打印出 1 到 100 之间的质数。有关基于数组的练习，请参见 Bubble 排序 Java 和 Java 数组，并审查 对于每个循环 Java 用于其他循环语法。

常见问题