Java rekursive Fibonacci-Sequenz

156

Bitte erläutern Sie diesen einfachen Code:

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Ich bin mit der letzten Zeile verwirrt, vor allem, weil wenn beispielsweise n = 5 ist, Fibonacci (4) + Fibonacci (3) usw. aufgerufen werden, aber ich verstehe nicht, wie dieser Algorithmus den Wert bei Index 5 damit berechnet Methode. Bitte erklären Sie mit viel Detail!

Index Hacker
quelle
8
Beachten Sie, dass dies rekursiv ist und in exponentieller Zeit ausgeführt wird. Es ist für große Werte von N ineffizient. Mit einem iterativen Ansatz konnte ich die ersten 10.000 Zahlen in der Sequenz berechnen. Sie können hier gefunden werden - goo.gl/hnbF5
Adam
@AdamFisher: Können Sie bitte den Code teilen, den Sie für die Berechnung von 10.000 Zahlen nacheinander verwendet haben? Ich bin eigentlich neugierig, es zu wissen.
Shumail
4
@AdamFisher Der Link, auf den Sie verwiesen haben, ist tot.
iRuth
2
Dieses Video erklärt, um die rekursive Funktion in 10 Minuten zu verstehen. Youtube.com/watch?v=t4MSwiqfLaY
Chathura Palihakkara
2
Es gibt auch einen iterativen Ansatz, der für Sie möglicherweise weniger schwierig ist. Großartiger Artikel über Rekursive und Iterative mit Code hier - codeflex.co/java-get-fibonacci-number-by-index
user5495300

Antworten:

165

In der Fibonacci-Sequenz ist jedes Element die Summe der beiden vorherigen. Sie haben also einen rekursiven Algorithmus geschrieben.

So,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

Jetzt weißt du es schon fibonacci(1)==1 and fibonacci(0) == 0. So können Sie anschließend die anderen Werte berechnen.

Jetzt,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

Und aus der Fibonacci-Sequenz können 0,1,1,2,3,5,8,13,21....wir sehen, dass für 5th elementdie Fibonacci-Sequenz zurückkehrt 5.

Das Rekursions-Tutorial finden Sie hier .

RanRag
quelle
Es wird funktionieren, aber nicht optimiert, bis es optimiert ist. Bitte schauen Sie sich meine Antwort an. Lassen Sie mich im Falle von Vorschlägen / Kommentaren wissen
M Sach
52

Es gibt 2 Probleme mit Ihrem Code:

  1. Das Ergebnis wird in int gespeichert, das nur die ersten 48 Fibonacci-Zahlen verarbeiten kann. Danach ist die Ganzzahlfüllung minus Bit und das Ergebnis falsch.
  2. Aber man kann niemals Fibonacci (50) ausführen.
    Der Code
    fibonacci(n - 1) + fibonacci(n - 2)
    ist sehr falsch.
    Das Problem ist, dass es Fibonacci nicht 50 Mal nennt, sondern viel mehr.
    Zuerst nennt es Fibonacci (49) + Fibonacci (48),
    dann Fibonacci (48) + Fibonacci (47) und Fibonacci (47) + Fibonacci (46).
    Jedes Mal, wenn es Fibonacci (n) schlechter wurde, ist die Komplexität exponentiell. Geben Sie hier die Bildbeschreibung ein

Der Ansatz für nicht rekursiven Code:

 double fibbonaci(int n){
    double prev=0d, next=1d, result=0d;
    for (int i = 0; i < n; i++) {
        result=prev+next;
        prev=next;
        next=result;
    }
    return result;
}
chro
quelle
4
Obwohl einige der anderen Antworten die Rekursion klarer erklären, ist dies wahrscheinlich die relevanteste Antwort auf einer tieferen Ebene.
Hal50000
1
Was bedeutet "Ganzzahlfüllung minus Bit"?
Richard
1
@richard, es geht darum, wie Integer gespeichert werden. Nachdem int 2 ^ 31-1 erreicht hat, handelt es sich beim nächsten Bit um ein Vorzeichen, sodass die Zahl negativ wird.
Chro
Viel schneller als rekursiv. Die einzige Einschränkung ist, dass es für n = 1 nicht funktioniert. Zusätzliche Bedingung ist erforderlich
v0rin
1
"Jedes Mal, wenn es 2 ^ n schlechter wurde" ist tatsächlich die Anzahl der gesamten Funktionsaufrufe 2*fibonacci(n+1)-1, so dass es mit der gleichen Komplexität wächst wie die Fibonacci-Zahlen selbst, die 1,618 ^ n anstelle von 2 ^ n
Aemyl sind
37

Im Pseudocode mit n = 5 findet Folgendes statt:

Fibonacci (4) + Fibonnacci (3)

Dies gliedert sich in:

(Fibonacci (3) + Fibonnacci (2)) + (Fibonacci (2) + Fibonnacci (1))

Dies gliedert sich in:

((((Fibonacci (2) + Fibonnacci (1)) + ((Fibonacci (1) + Fibonnacci (0))) + ((((Fibonacci (1) + Fibonnacci (0)) + 1))

Dies gliedert sich in:

(((((Fibonacci (1) + Fibonnacci (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Dies gliedert sich in:

((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Das führt zu: 5

Wenn die Fibonnacci-Sequenz 1 1 2 3 5 8 ... ist , ist das 5. Element 5. Sie können dieselbe Methode verwenden, um die anderen Iterationen herauszufinden.

Dan Hardiker
quelle
Ich denke, diese Antwort erklärt die Fragen am besten. Wirklich einfach
Amit
Das ist ordentlich. Erklärt sowohl den Wert am n-ten Term als auch die darauf folgende Reihe.
Semikolon
12

Rekursion kann manchmal schwer zu erfassen sein. Bewerten Sie es einfach auf einem Blatt Papier für eine kleine Anzahl:

fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3

Ich bin nicht sicher, wie Java dies tatsächlich bewertet, aber das Ergebnis wird das gleiche sein.

tim
quelle
Woher kommen in der zweiten Zeile die 1 und 0 am Ende?
Pocockn
1
@pocockn fib (2) = fib (1) + fib (0)
Tim
Sie haben also fib (4), also wären n-1 und n-2 fib (3) + fib (2), dann machen Sie n-1 und n-2 erneut, und Sie erhalten -> fib (2) + fib (1) ), woher hast du die + fib (1) + fib (0)? Am Ende hinzugefügt
pocockn
@pocockn fib (2) + fib (1) ist von fib (3), fib (1) + fib (0) ist von fib (2)
tim
12

Sie können Ihre Funktion auch wie folgt vereinfachen:

public int fibonacci(int n)  {
    if (n < 2) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}
Otavio Ferreira
quelle
Wie unterscheidet sich das von diesem oder jenem oder dieser Antwort?
Tunaki
6
Es ist nur kürzer und einfacher zu lesen, welche Algorithmen immer sein sollten =)
Otavio Ferreira
@OtavioFerreira die einzige Antwort, die es geschafft hat, mein Problem zu lösen, gute Arbeit
KKKKK
8
                                F(n)
                                /    \
                            F(n-1)   F(n-2)
                            /   \     /      \
                        F(n-2) F(n-3) F(n-3)  F(n-4)
                       /    \
                     F(n-3) F(n-4)

Es ist wichtig zu beachten, dass dieser Algorithmus exponentiell ist, da er nicht das Ergebnis zuvor berechneter Zahlen speichert. zB F (n-3) wird 3 mal aufgerufen.

Weitere Einzelheiten finden Sie im Algorithmus von dasgupta, Kapitel 0.2

Amandeep Kamboj
quelle
Es gibt eine Programmiermethode, mit der wir vermeiden können, F (n) für dasselbe n immer wieder mit dynamischer Programmierung zu
berechnen
8

Die meisten Antworten sind gut und erklären, wie die Rekursion in Fibonacci funktioniert.

Hier ist eine Analyse der drei Techniken, die auch die Rekursion umfasst:

  1. Für Schleife
  2. Rekursion
  3. Auswendiglernen

Hier ist mein Code zum Testen aller drei:

public class Fibonnaci {
    // Output = 0 1 1 2 3 5 8 13

    static int fibMemo[];

    public static void main(String args[]) {
        int num = 20;

        System.out.println("By For Loop");
        Long startTimeForLoop = System.nanoTime();
        // returns the fib series
        int fibSeries[] = fib(num);
        for (int i = 0; i < fibSeries.length; i++) {
            System.out.print(" " + fibSeries[i] + " ");
        }
        Long stopTimeForLoop = System.nanoTime();
        System.out.println("");
        System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));


        System.out.println("By Using Recursion");
        Long startTimeRecursion = System.nanoTime();
        // uses recursion
        int fibSeriesRec[] = fibByRec(num);

        for (int i = 0; i < fibSeriesRec.length; i++) {
            System.out.print(" " + fibSeriesRec[i] + " ");
        }
        Long stopTimeRecursion = System.nanoTime();
        System.out.println("");
        System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));



        System.out.println("By Using Memoization Technique");
        Long startTimeMemo = System.nanoTime();
        // uses memoization
        fibMemo = new int[num];
        fibByRecMemo(num-1);
        for (int i = 0; i < fibMemo.length; i++) {
            System.out.print(" " + fibMemo[i] + " ");
        }
        Long stopTimeMemo = System.nanoTime();
        System.out.println("");
        System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));

    }


    //fib by memoization

    public static int fibByRecMemo(int num){

        if(num == 0){
            fibMemo[0] = 0;
            return 0;
        }

        if(num ==1 || num ==2){
          fibMemo[num] = 1;
          return 1; 
        }

        if(fibMemo[num] == 0){
            fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
            return fibMemo[num];
        }else{
            return fibMemo[num];
        }

    }


    public static int[] fibByRec(int num) {
        int fib[] = new int[num];

        for (int i = 0; i < num; i++) {
            fib[i] = fibRec(i);
        }

        return fib;
    }

    public static int fibRec(int num) {
        if (num == 0) {
            return 0;
        } else if (num == 1 || num == 2) {
            return 1;
        } else {
            return fibRec(num - 1) + fibRec(num - 2);
        }
    }

    public static int[] fib(int num) {
        int fibSum[] = new int[num];
        for (int i = 0; i < num; i++) {
            if (i == 0) {
                fibSum[i] = i;
                continue;
            }

            if (i == 1 || i == 2) {
                fibSum[i] = 1;
                continue;
            }

            fibSum[i] = fibSum[i - 1] + fibSum[i - 2];

        }
        return fibSum;
    }

}

Hier sind die Ergebnisse:

By For Loop
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
For Loop Time:347688
By Using Recursion
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Recursion Time:767004
By Using Memoization Technique
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Memoization Time:327031

Daher können wir sehen, dass das Auswendiglernen zeitlich und für Schleifenübereinstimmungen am besten ist .

Aber die Rekursion dauert am längsten und sollte im wirklichen Leben vermieden werden. Stellen Sie auch bei Verwendung der Rekursion sicher, dass Sie die Lösung optimieren.

Pritam Banerjee
quelle
1
"Hier können wir sehen, dass die Schleife die beste Zeit ist"; "Für die Schleifenzeit: 347688"; "Memoization Time: 327031"; 347688> 327031.
AjahnCharles
@CodeConfident Ja, ich habe diesen Fehler heute gerade gesehen und wollte ihn korrigieren. Trotzdem danke :).
Pritam Banerjee
7

Dies ist das beste Video, das ich gefunden habe und das die Rekursion und die Fibonacci-Sequenz in Java vollständig erklärt.

http://www.youtube.com/watch?v=dsmBRUCzS7k

Dies ist sein Code für die Sequenz und seine Erklärung ist besser, als ich jemals versuchen könnte, sie abzutippen.

public static void main(String[] args)
{
    int index = 0;
    while (true)
    {
        System.out.println(fibonacci(index));
        index++;
    }
}
    public static long fibonacci (int i)
    {
        if (i == 0) return 0;
        if (i<= 2) return 1;

        long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
        return fibTerm;
    }
user2718538
quelle
5

Für eine rekursive Fibonacci-Lösung ist es wichtig, die Ausgabe kleinerer Fibonacci-Zahlen zu speichern und gleichzeitig den Wert einer größeren Zahl abzurufen. Dies wird als "Auswendiglernen" bezeichnet.

Hier ist ein Code, der das Speichern der kleineren Fibonacci-Werte beim Abrufen einer größeren Fibonacci-Zahl verwendet. Dieser Code ist effizient und stellt nicht mehrere Anforderungen derselben Funktion.

import java.util.HashMap;

public class Fibonacci {
  private HashMap<Integer, Integer> map;
  public Fibonacci() {
    map = new HashMap<>();
  }
  public int findFibonacciValue(int number) {
    if (number == 0 || number == 1) {
      return number;
    }
    else if (map.containsKey(number)) {
      return map.get(number);
    }
    else {
      int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
      map.put(number, fibonacciValue);
      return fibonacciValue;
    }
  }
}
Amarjit Datta
quelle
4

In der Fibonacci- Sequenz sind die ersten beiden Elemente 0 und 1, wobei jedes andere Element die Summe der beiden vorherigen Elemente ist. dh:
0 1 1 2 3 5 8 ...

Das fünfte Element ist also die Summe aus dem vierten und dem dritten Element.

Yurib
quelle
4

Michael Goodrich et al. Bieten einen wirklich cleveren Algorithmus in Datenstrukturen und Algorithmen in Java, um Fibonacci rekursiv in linearer Zeit zu lösen, indem ein Array von [fib (n), fib (n-1)] zurückgegeben wird.

public static long[] fibGood(int n) {
    if (n < = 1) {
        long[] answer = {n,0};
        return answer;
    } else {
        long[] tmp = fibGood(n-1);
        long[] answer = {tmp[0] + tmp[1], tmp[0]};
        return answer;
    }
}

Dies ergibt fib (n) = fibGood (n) [0].

Rae
quelle
4

Hier ist O (1) -Lösung:

 private static long fibonacci(int n) {
    double pha = pow(1 + sqrt(5), n);
    double phb = pow(1 - sqrt(5), n);
    double div = pow(2, n) * sqrt(5);

    return (long) ((pha - phb) / div);
}

Binets Fibonacci-Zahlenformel, die für die obige Implementierung verwendet wurde. Bei großen Eingängen longkann durch ersetzt werden BigDecimal.

Samir
quelle
3

Eine Fibbonacci-Sequenz ist eine Sequenz, die das Ergebnis einer Zahl summiert, wenn sie zum vorherigen Ergebnis hinzugefügt wird, beginnend mit 1.

      so.. 1 + 1 = 2
           2 + 3 = 5
           3 + 5 = 8
           5 + 8 = 13
           8 + 13 = 21

Sobald wir verstanden haben, was Fibbonacci ist, können wir beginnen, den Code aufzuschlüsseln.

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Die erste if-Anweisung sucht nach einem Basisfall, in dem die Schleife ausbrechen kann. Die else if-Anweisung darunter macht dasselbe, könnte aber so umgeschrieben werden ...

    public int fibonacci(int n)  {
        if(n < 2)
             return n;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

Nachdem ein Basisfall erstellt wurde, müssen wir den Aufrufstapel verstehen. Ihr erster Aufruf von "Fibonacci" wird der letzte sein, der auf dem Stapel (Reihenfolge der Aufrufe) aufgelöst wird, da sie in der umgekehrten Reihenfolge aufgelöst werden, aus der sie aufgerufen wurden. Die letzte aufgerufene Methode wird zuerst aufgelöst, dann die letzte, die vor dieser aufgerufen wird, und so weiter ...

Alle Anrufe werden also zuerst getätigt, bevor mit diesen Ergebnissen etwas "berechnet" wird. Bei einer Eingabe von 8 erwarten wir eine Ausgabe von 21 (siehe Tabelle oben).

Fibonacci (n - 1) wird so lange aufgerufen, bis es den Basisfall erreicht, dann wird Fibonacci (n - 2) aufgerufen, bis es den Basisfall erreicht. Wenn der Stapel beginnt, das Ergebnis in umgekehrter Reihenfolge zu summieren, sieht das Ergebnis so aus ...

1 + 1 = 1        ---- last call of the stack (hits a base case).
2 + 1 = 3        ---- Next level of the stack (resolving backwards).
2 + 3 = 5        ---- Next level of the stack (continuing to resolve).

Sie sprudeln weiter (werden rückwärts aufgelöst), bis die richtige Summe an den ersten Aufruf im Stapel zurückgegeben wird und Sie auf diese Weise Ihre Antwort erhalten.

Allerdings ist dieser Algorithmus sehr ineffizient, da er für jeden Zweig, in den sich der Code aufteilt, das gleiche Ergebnis berechnet. Ein viel besserer Ansatz ist ein "Bottom-up" -Ansatz, bei dem keine Memoisierung (Caching) oder Rekursion (Deep Call Stack) erforderlich ist.

Wie so ...

        static int BottomUpFib(int current)
        {
            if (current < 2) return current;

            int fib = 1;
            int last = 1;

            for (int i = 2; i < current; i++)
            {
                int temp = fib;
                fib += last;
                last = temp;
            }

            return fib;
        }
Jeffrey Ferreiras
quelle
2

Die meisten hier angebotenen Lösungen laufen in O (2 ^ n) -Komplexität. Die Neuberechnung identischer Knoten im rekursiven Baum ist ineffizient und verschwendet CPU-Zyklen.

Wir können die Memoisierung verwenden, um die Fibonacci-Funktion in O (n) -Zeit ausführen zu lassen

public static int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

public static int fibonacci(int i, int[] memo) {

    if (i == 0 || i == 1) {
        return i;
    }

    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return memo[i];
}

Wenn wir der dynamischen Programmierroute von unten nach oben folgen, ist der folgende Code einfach genug, um Fibonacci zu berechnen:

public static int fibonacci1(int n) {
    if (n == 0) {
        return n;
    } else if (n == 1) {
        return n;
    }
    final int[] memo = new int[n];

    memo[0] = 0;
    memo[1] = 1;

    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n - 1] + memo[n - 2];
}
realPK
quelle
2

Warum diese Antwort anders ist

Jede andere Antwort entweder:

  • Druckt statt zurück
  • Führt 2 rekursive Aufrufe pro Iteration durch
  • Ignoriert die Frage mithilfe von Schleifen

(abgesehen davon: keines davon ist tatsächlich effizient; verwenden Sie die Binet-Formel , um das n- te direkt zu berechnen Term )

Schwanz rekursive Fib

Hier ist ein rekursiver Ansatz, der einen doppelt rekursiven Aufruf vermeidet, indem sowohl die vorherige als auch die vorherige Antwort übergeben werden.

private static final int FIB_0 = 0;
private static final int FIB_1 = 1;

private int calcFibonacci(final int target) {
    if (target == 0) { return FIB_0; }
    if (target == 1) { return FIB_1; }

    return calcFibonacci(target, 1, FIB_1, FIB_0);
}

private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
    final int current = previous + 1;
    final int fibCurrent = fibPrevious + fibPreviousMinusOne;
    // If you want, print here / memoize for future calls

    if (target == current) { return fibCurrent; }

    return calcFibonacci(target, current, fibCurrent, fibPrevious);
}
AjahnCharles
quelle
1

Es ist eine Grundsequenz, die 1 1 2 3 5 8 anzeigt oder eine Ausgabe von 1 1 2 3 5 8 erhält. Es ist eine Sequenz, bei der die Summe der vorherigen Nummer und der aktuellen Nummer als nächstes angezeigt wird.

Versuchen Sie, den Link unter dem Java Tutorial für rekursive Fibonacci-Sequenzen zu sehen

public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}

Klicken Sie hier Sehen Sie sich das Java Recursive Fibonacci-Sequenz-Tutorial für die Löffelfütterung an

Jaymelson Galang
quelle
Was er verstehen musste, war, wie der Code funktioniert und warum er so geschrieben wird, wie er geschrieben ist.
Adarsh
Ich denke, ich erwähne in meinem ersten Satz, wie es funktioniert? Ich schreibe den Code, um es einfacher zu machen. Übrigens, sorry.
Jaymelson Galang
An Ihrem Code ist nichts auszusetzen. Nur der Typ wollte verstehen, wie dieser Code funktioniert. Überprüfen Sie die Antwort von RanRag. Etwas in dieser Art :)
Adarsh
ahh ok, sorry ich bin Anfänger hier im Stackoverflow.
Ich
1

Ich denke, das ist ein einfacher Weg:

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        long a = 0;
        long b = 1;
        for(int i = 1; i<number;i++){
            long c = a +b;
            a=b;
            b=c;
            System.out.println(c);
        }
    }
}
user3787713
quelle
1

Die RanRag-Antwort (akzeptiert) funktioniert einwandfrei, aber dies ist keine optimierte Lösung, bis sie gespeichert wird, wie in Anil-Antwort erläutert.

Für den rekursiven Ansatz unten sind Methodenaufrufe von TestFibonacciminimal

public class TestFibonacci {

    public static void main(String[] args) {

        int n = 10;

        if (n == 1) {
            System.out.println(1);

        } else if (n == 2) {
            System.out.println(1);
            System.out.println(1);
        } else {
            System.out.println(1);
            System.out.println(1);
            int currentNo = 3;
            calFibRec(n, 1, 1, currentNo);
        }

    }

    public static void calFibRec(int n, int secondLast, int last,
            int currentNo) {
        if (currentNo <= n) {

            int sum = secondLast + last;
            System.out.println(sum);
            calFibRec(n, last, sum, ++currentNo);
        }
    }

}
M Sach
quelle
1
public class febo 
{
 public static void main(String...a)
 {
  int x[]=new int[15];  
   x[0]=0;
   x[1]=1;
   for(int i=2;i<x.length;i++)
   {
      x[i]=x[i-1]+x[i-2];
   }
   for(int i=0;i<x.length;i++)
   {
      System.out.println(x[i]);
   }
 }
}
msanford
quelle
1

Durch die Verwendung einer internen ConcurrentHashMap, die theoretisch den ordnungsgemäßen Betrieb dieser rekursiven Implementierung in einer Multithread-Umgebung ermöglichen könnte, habe ich eine Fib-Funktion implementiert, die sowohl BigInteger als auch Recursion verwendet. Die Berechnung der ersten 100 Fib-Zahlen dauert ca. 53 ms.

private final Map<BigInteger,BigInteger> cacheBig  
    = new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
    BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
    return a;
}
public BigInteger fibBigCache(BigInteger n) {
    if ( n.compareTo(BigInteger.ONE ) <= 0 ){
        return n;
    } else if (cacheBig.containsKey(n)){
        return cacheBig.get(n);
    } else {
        return      
            fibBigCache(n.subtract(BigInteger.ONE))
            .add(fibBigCache(n.subtract(TWO)));
    }
}

Der Testcode lautet:

@Test
public void testFibRecursiveBigIntegerCache() {
    long start = System.currentTimeMillis();
    FibonacciSeries fib = new FibonacciSeries();
    IntStream.rangeClosed(0,100).forEach(p -&R {
        BigInteger n = BigInteger.valueOf(p);
        n = fib.fibRecursiveBigCache(n);
        System.out.println(String.format("fib of %d is %d", p,n));
    });
    long end = System.currentTimeMillis();
    System.out.println("elapsed:" + 
    (end - start) + "," + 
    ((end - start)/1000));
}
und die Ausgabe des Tests ist:
    .
    .
    .
    .
    .
    fib von 93 ist 12200160415121876738
    fib von 94 ist 19740274219868223167
    fib von 95 ist 31940434634990099905
    fib von 96 ist 51680708854858323072
    fib von 97 ist 83621143489848422977
    fib von 98 ist 135301852344706746049
    fib von 99 ist 218922995834555169026
    fib von 100 ist 354224848179261915075
    verstrichen: 58,0
George Curington
quelle
1

Hier ist eine einzeilige febonacci rekursive:

public long fib( long n ) {
        return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
RonTLV
quelle
1

Versuche dies

private static int fibonacci(int n){
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
Markus Rytter
quelle
0

Wenn Sie größere Zahlen berechnen möchten, sollten Sie BigInteger verwenden.

Ein iteratives Beispiel.

import java.math.BigInteger;
class Fibonacci{
    public static void main(String args[]){
        int n=10000;
        BigInteger[] vec = new BigInteger[n];
        vec[0]=BigInteger.ZERO;
        vec[1]=BigInteger.ONE;
        // calculating
        for(int i = 2 ; i<n ; i++){
            vec[i]=vec[i-1].add(vec[i-2]);
        }
        // printing
        for(int i = vec.length-1 ; i>=0 ; i--){
            System.out.println(vec[i]);
            System.out.println("");
        }
    }
}
Tiago Zortea
quelle
0

http://en.wikipedia.org/wiki/Fibonacci_number in weiteren Details

public class Fibonacci {

    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        for (int i = 1; i <= N; i++)
            System.out.println(i + ": " + fib(i));
    }

}

Machen Sie es so einfach wie nötig, ohne dass Sie while-Schleifen und andere Schleifen verwenden müssen

vikas
quelle
0
public class FibonacciSeries {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        for (int i = 0; i <= N; i++) {
            int result = fibonacciSeries(i);
            System.out.println(result);
        }
        scanner.close();
    }

    private static int fibonacciSeries(int n) {
        if (n < 0) {
            return 1;
        } else if (n > 0) {
            return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
        }
        return 0;
    }
}
user3231661
quelle
0

Verwendung while:

public int fib(int index) {
    int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
    while (tmp < index - 1) {
        fibNumber = step1 + step2;
        step1 = step2;
        step2 = fibNumber;
        tmp += 1;
    };
    return fibNumber;
}

Der Vorteil dieser Lösung ist, dass es einfach ist, den Code zu lesen und zu verstehen, in der Hoffnung, dass er hilft

Gavriel Cohen
quelle
0

Eine Fibbonacci-Sequenz ist eine, die das Ergebnis einer Zahl summiert, die wir dann zum vorherigen Ergebnis hinzugefügt haben. Wir sollten mit 1 beginnen. Ich habe versucht, eine Lösung basierend auf dem Algorithmus zu finden, also habe ich den rekursiven Code erstellt und festgestellt, dass ich die behalte vorherige Nummer und ich habe die Position geändert. Ich suche die Fibbonacci-Sequenz von 1 bis 15.

public static void main(String args[]) {

    numbers(1,1,15);
}


public static int numbers(int a, int temp, int target)
{
    if(target <= a)
    {
        return a;
    }

    System.out.print(a + " ");

    a = temp + a;

    return numbers(temp,a,target);
}
Mathias Stavrou
quelle
-1
 public static long fib(int n) {
    long population = 0;

    if ((n == 0) || (n == 1)) // base cases
    {
        return n;
    } else // recursion step
    {

        population+=fib(n - 1) + fib(n - 2);
    }

    return population;
}
Ian Mukunya Douglas
quelle
-1

Einfache Fibonacci

public static void main(String[]args){

    int i = 0;
    int u = 1;

    while(i<100){
        System.out.println(i);
        i = u+i;
        System.out.println(u);
        u = u+i;
    }
  }
}
Marcxcx
quelle
2
Willkommen bei SO. Während Ihre Antwort die Fibonacci-Sequenz berechnet. Ihre Antwort beantwortet nicht das OP, das nach rekursiven Funktionen gefragt hat.
James K
-2

@chro ist genau richtig, aber er / sie zeigt nicht den richtigen Weg, um dies rekursiv zu tun. Hier ist die Lösung:

class Fib {
    static int count;

    public static void main(String[] args) {
        log(fibWrong(20));  // 6765
        log("Count: " + count); // 21891
        count = 0;
        log(fibRight(20)); // 6765
        log("Count: " + count); // 19
    }

    static long fibRight(long n) {
        return calcFib(n-2, 1, 1);
    }

    static long fibWrong(long n) {
        count++;
        if (n == 0 || n == 1) {
            return n;
        } else if (n < 0) {
            log("Overflow!");
            System.exit(1);
            return n;
        } else {
            return fibWrong(n-1) + fibWrong(n-2);
        }

    }

    static long calcFib(long nth, long prev, long next) {
        count++;
        if (nth-- == 0)
            return next;
        if (prev+next < 0) {
            log("Overflow with " + (nth+1) 
                + " combinations remaining");
            System.exit(1);
        }
        return calcFib(nth, next, prev+next);
    }

    static void log(Object o) {
        System.out.println(o);
    }
}
taylordurden
quelle