Fibonacci-serien in Java med hjälp av rekursion och loopar

⚡ Smart sammanfattning

Fibonacci-serien in Java genererar en sekvens där varje term är lika med summan av de två föregående termerna. Den här artikeln presenterar for loop, while loop, användarinmatning, rekursiva och memo-baserade program, tracanalyserar rekursionen och jämför tidskomplexiteten för varje metod.

  • ➕ Kärnregel: Varje term är summan av de två föregående termerna, och talföljden börjar med 0 och 1.
  • 🔁 Iterativt mönster: Två variabler håller föregående och nästa värde, och en tillfällig summa flyttar dem framåt vid varje pass.
  • 🌀 Rekursivt mönster: Metoden anropar sig själv två gånger per term, med 0, 1 och 2 som basfall.
  • ⏱️ Komplexitetsgap: Loopar körs i O(n)-tid medan naiv rekursion körs i O(2ⁿ), vilket blir oanvändbart efter ungefär 40 termer.
  • 🧠 Åtgärd för memohantering: Cachning av beräknade termer i en array återställer linjär tid medan keeping den rekursiva strukturen.
  • ⚠️ Överfyllnadsgräns: Den 47:e termen överskrider int-intervallet, så long eller BigInteger krävs för längre sekvenser.
  • ⌨️ Användarinmatning: Klassen Scanner läser önskat antal vid körning utan att ändra någon av genereringslogiken.

Fibonacci-serien in Java

Vad är Fibonacci-serien i Java?

A Fibonacci-serien in Java är en talserie där nästa tal är summan av de två föregående talen. De två första talen i Fibonacciserien är 0 och 1. Fibonaccitalen används i stor utsträckning i den beräkningsmässiga körtidsstudien av algoritmen som bestämmer den största gemensamma delaren av två heltal.

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

Uttryckt som en formel är regeln F(n) = F(n-1) + F(n-2), med F(0) = 0 och F(1) = 1. Tabellen nedan visar hur de första åtta termerna produceras.

Position (n) Beräkning Värderar
0 Basfodral 0
1 Basfodral 1
2 0 + 1 1
3 1 + 1 2
4 1 + 2 3
5 2 + 3 5
6 3 + 5 8
7 5 + 8 13

Fibonacci-seriens program i Java använder For Loop

Den iterativa versionen lagrar endast två värden i minnet åt gången, vilket är anledningen till att den körs i linjär tid och konstant rum.

//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;
	        }
	}
}

Produktion:

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

Programlogik:

  • föregåendeNummer initieras till 0 och nästaNummer initieras till 1.
  • Fibonacci-for-loopen itererar igenom maxNumber:
    • Visa föregående nummer.
    • Beräkna summan av föregåendeNummer och nästaNummer.
    • Uppdatera de nya värdena för previousNumber och nextNumber.

Fibonacci-seriens program i Java använder While Loop

Du kan också generera en Java Fibonacciserier med hjälp av en while slinga in JavaAritmetiken är identisk, och endast loopsyntaxen ändras.

//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++;
	        }

	}

}

Produktion:

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

Den enda skillnaden i programlogiken är användningen av en while-loop för att skriva ut Fibonacci-talen. Räknaren måste deklareras före loopen och ökas inuti den, annars slutar loopen aldrig.

Fibonacci-serien baserad på användarinmatningen

Att hårdkoda termantalet är praktiskt för en demonstration, men verkliga övningar läser vanligtvis värdet från tangentbordet. Klassen Scanner hanterar det på tre rader, och genereringslogiken förblir orörd.

//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();
    }
}

Provkörning:

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

Programlogik:
Logiken är densamma som tidigare. Istället för att hårdkoda antalet element som ska visas i Java Fibonacciserien, användaren ombeds att ange ett tal.

Fibonacci-serien använder rekursion i Java

Nedan finns ett program i Fibonacci-serien Java använder rekursion:

//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) +" ");
		}
	}
}

Produktion:

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

Programlogik:

En rekursiv funktion är en som har förmågan att anropa sig själv.

fibonacciRecursion():

  1. Ocuco-landskapet Java Fibonacci-rekursionsfunktionen tar ett inmatningstal. Den kontrollerar 0, 1 och 2 och returnerar 0, 1 respektive 1, eftersom Fibonacci-sekvensen i Java börjar med 0, 1, 1.
  2. När inmatningen n är 3 eller större anropar funktionen sig själv rekursivt. Anropet görs två gånger. trace nedan följer uppmaningen för inmatning av 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

Basfallen stoppar nedstigningen. Eftersom 1 och 2 båda återvänder omedelbart, expanderar grenen för fibonacciRecursion(2) aldrig ytterligare, vilket är det som håller trace ändlig.

Optimerade Fibonacci-serier med hjälp av memoisering

Enkel rekursion beräknar samma termer om många gånger. Beräkning av term 40 kräver mer än 200 miljoner anrop. Att lagra varje resultat första gången det beräknas tar bort den dubbleringen helt.

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));
    }
}

Produktion:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

⚠️ Varning: Den 47:e Fibonaccitermen är 2971215073, vilket överstiger det maximala int-värdet på 2147483647 och radbryts till ett negativt värde. Deklarera variablerna lika länge när antalet passerar 46, och byt till BigInteger efter term 92.

Jämförelse av Fibonacci-metoder i Java

Alla fyra programmen skriver ut samma sekvens, så beslutet vilar på hur många termer som behövs.

Metod Tidskomplexitet Rymdkomplexitet Praktisk gräns
För slinga O (n) O (1) Valfritt antal, beroende på den numeriska typen
Medan slinga O (n) O (1) Valfritt antal, beroende på den numeriska typen
Enkel rekursion O(2ⁿ) O(n)-stack Runt 40 termer innan det blir långsamt
Rekursion med memoisering O (n) O (n) Valfritt antal, beroende på den numeriska typen

Samma räknar- och ackumulatormönster förekommer i flera relaterade övningar. Fortsätt med Java palindromprogram, den Java program för att kontrollera ett primtal, Och den program för att skriva ut primtal från 1 till 100För arraybaserad övning, se Bubble Sortera i Java och Java arrayeroch granska för varje slinga i Java för alternativ loopsyntax.

Vanliga frågor

Båda konventionerna existerar. Datavetenskap använder normalt 0 och 1 som de två första termerna, vilket är vad dessa program gör. Vissa matematiska texter börjar istället på 1 och 1.

Varje anrop skapar ytterligare två anrop, så arbetet fördubblas med varje extra term. Samma delproblem löses upprepade gånger, vilket ger en exponentiell tillväxt i antalet anrop.

Ett heltal innehåller termer upp till nummer 46, och ett långt tal innehåller termer upp till nummer 92. Utöver det krävs BigInteger eftersom värdena överstiger 64 bitar.

Konsekutiva termer närmar sig det gyllene snittet, ungefär 1.618. Mönstret förekommer i bladarrangemang, skalspiraler, agila uppskattningsskalor och teknisk analys inom handel.

De returnerar ofta ren rekursion eftersom det är det vanligaste läroboksexemplet. Be explicit om en iterativ eller memoariserad lösning när termantalet är stort.

Det är det minsta problemet där caching överlappar varandraping Delproblem ger en dramatisk hastighetsökning. Samma princip ligger till grund för memobaserad sökning och värdecachning i AI-planeringsalgoritmer.

Sammanfatta detta inlägg med: