Rekursive Funktionen, Die Mit Fibonacci-Reihe

Bin ich selbst-lernen C++ von Sams Teach Yourself C++ In Einer Stunde Ein Tag und auf Seite 150 der Autor beschreibt rekursive Funktionen mit Hilfe der Fibonacci-Reihe.

Er verwendet den folgenden code:

#include <iostream>
using namespace std;

int GetFibNumber(int FibIndex)
{
    if(FibIndex < 2 )
        return FibIndex;
    else
        return GetFibNumber(FibIndex - 1) + GetFibNumber(FibIndex - 2);
}

int main()
{
    cout << " Enter 0 based index of desired Fibonacci Number: ";
    int Index = 0;
    cin >> Index;

    cout << " Fibonacci number is: " << GetFibNumber(Index) << endl;

    return 0;

}

Was ist der Unterschied zwischen

zurück GetFibNumber(FibIndex - 1) + GetFibNumber(FibIndex - 2);

und

zurück FibIndex - 1 + FibIndex - 2;

Warum haben Sie zum Aufruf der Funktion in sich selbst?

Vielen Dank im Voraus!

Könntest du bitte ein Beispiel geben, was du hast, und erläutern Sie Ihre Frage deutlicher.
Was bedeutet die Linie 9 jetzt Lesen? Ohne diese beiden Funktion Aufrufe, es wird nicht die Berechnung der Fibonacci-Folge.
Bitte werfen Sie einen Blick auf, was die Fibonacci-Reihe ist en.wikipedia.org/wiki/Fibonacci_number Ohne die Letzte GetFibNumber(FibIndex - 1) + GetFibNumber(FibIndex - 2) Berechnung ist falsch.
Ja, ich bin mir bewusst, dass. Ich einfach entfernt "GetFibNumber" in der Zeile, die Sie gerade kopiert und eingefügt werden.
Es wird funktionieren, solange der input-parameter FibIndex ist klein (< 4). 10 nehmen zum Beispiel. Die 10 fibonnaci-Nummer 34. Aber mit deiner Berechnung, die Sie erhalten (10-1 + 10 -2 = 17)
Ich habe aktualisiert die Frage. Das einzige, was ich angepasst, in meiner version war return FibIndex - 1 + FibIndex - 2;

InformationsquelleAutor JOG-Design | 2013-12-17

c++fibonacci recursion

2

Fragen Sie: "Warum haben Sie zum Aufruf der Funktion in sich selbst?" Gut, streng, Sie nicht.

Den Fibonacci-Folge ist die Folge von zahlen definiert, die von diesem mathematische Rekursion:
- a₀ = 0
- a₁ = 1
- a_n = a_n-1 + a_n-2
Die ursprüngliche Funktion nicht berechnen Sie diese Reihenfolge, wenn auch ineffizient. Wenn Index 0 ist, wird 0 zurückgegeben; wenn es 1 ist, gibt Sie 1 zurück. Ansonsten gibt es GetFibNumber(Index - 1) + GetFibNumber(Index - 2) genau das ist die mathematische definition ist. Für jedes element der Sequenz, müssen Sie die beiden vorherigen Begriffe in der Sequenz.

Den code kurz zurück Index - 1 + Index - 2, die verschiedenen numerischen Reihenfolge. Vergleichen:
- Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 36...
- Deins: 0, 1, 1, 3, 5, 7, 9, 11, 13, 17...
Aber das beiseite, die Sie nicht unbedingt brauchen eine rekursive Funktion zur Berechnung dieses mathematischen Rekursion. Alles, was Sie brauchen, ist eine einfache for Schleife:
```
int GetFibNumber(int FibIndex)
{

    if(FibIndex < 2 )
        return FibIndex;

    int a_n_2 = 0, a_n_1 = 1, a_n;

    for (i = 2; i < FibIndex; i++)
    {
        a_n = a_n_1 + a_n_2;
        a_n_2 = a_n_1;
        a_n_1 = a_n;
    }

    return a_n;
}
```
Dieser Ansatz ist sehr viel schneller, auch.

Den code-Rekursives Verfahren ist mathematisch korrekt. Es ist jedoch langsamer, weil es nicht die Wiederverwendung von Berechnungen. Es berechnet a_n-1 durch die überarbeitung der Rekursion den ganzen Weg zurück zu a₁. Es berechnet dann a_n-2, ohne bereits die Arbeit generiert, dass die a_n-1. Und wenn Sie denken, diese Mangel-of-Wiederverwendung passiert bei jedem Schritt der Rekursion, werden Sie sehen, dass die Laufzeit wächst exponentiell an, für die rekursive Funktion. Es wächst Linear für die for Schleife, obwohl.

_{Fortgeschrittene Thema: Es ist ein Weg, um die rekursive version schneller laufen, und das kann wichtig sein, zu wissen, wenn Sie ein Programmier-problem, das ist am einfachsten rekursiv definiert. Sobald Sie mehr Erfahrung mit C++, look-up -memoization. Ein memoized rekursive Fibonacci gibt lineare worst-case-Laufzeit und konstanter Laufzeit für wiederholte Suchvorgänge (vorausgesetzt, die memo-lookup ist sich O(1)).}
- Lol, durch das wissen, dass er nicht Programmieren müssen, um ein iteratives Programm nicht mehr, wie ich vorgeschlagen 🙂
- Ich denke, mehrere von uns allen beantwortet diese Frage in parallel. Manchmal, denke ich, dass Fragen wie diese sind ein Rorschach-Test. 😉
InformationsquelleAutor Joe Z
1

Mithilfe der version, die keine Rekursion ist nicht korrekt. Es wird nur berechnen, richtig ersten paar Fiboonacci zahlen. Versuchen Sie, um zu berechnen, ersten 10 Fibonacci-zahlen mit Hilfe der zwei Versionen und sehen Sie sich die zwei Versionen berechnen Sie zwei verschiedene Sequenzen.

InformationsquelleAutor Ivaylo Strandjev
1

Die Funktion GetFibNumber berechnet die N-te Zahl in der Fibonacci-Reihe. Wenn Sie nur einen Blick die Erklärung auf http://en.wikipedia.org/wiki/Fibonacci_number es wird berechnet, indem die N-1 und N-2 zahlen in der Fibinacci Serie. Und das ist genau das, was die Funktion tut. Stellen Sie die Funktion mit einem index in der Fibonacci-Reihe, die Sie berechnen möchten (angenommen 6; dies sollte 8 als Ergebnis).

Berechnen das 6. element der Fibonacci-Reihe müssen Sie den 5. und den 4 Elementen zusammen. So müssen Sie zunächst berechnen Sie diese. Dies ist, wo die Rekursion Schritte. Lassen Sie die Funktion sich selbst aufrufen; aber statt es wieder mit dem Wert 6 als parameter, den Sie jetzt verwenden Sie 5 und 4. Dies wird wiederum dazu führen, dass gleiche problem (müssen Sie calc 5th element durch hinzufügen von Elementen 4 und 3), etc. etc.

Mit der rekursiven Funktion können Sie ganz einfach wieder-verwenden Sie den code, um die gleiche Berechnung immer und immer wieder, bis man einen bestimmten Punkt erreicht, wo Sie eine Antwort haben, die für die Berechnung (in diesem Fall, wenn N = 1 oder N = 0; in diesen Fällen wird in Folge 1).

InformationsquelleAutor RFerwerda
1

Ich würde vorschlagen, da Sie noch lernen, um dieses Programm sowohl rekursiv (wie der Autor getan hat) und mit Hilfe einer Schleife (while, for). Es wird wahrscheinlich zeigen Sie die Antwort, wie dieser Algorithmus aufgebaut ist.

Tipp 1: Sie müssen wissen, dass die Fibonnaci-Sequenzen aufgebaut werden, bei der zwei Anfangswerte,...

Tipp 2: wenn es um Rekursion, sollten Sie wissen, wie die Funktion, die Ergebnisse gespeichert. Erklären, dass deine Frage als gut.

InformationsquelleAutor RvdV79
1

Sind Sie nicht equvialent, und es wird sicherlich nicht die Berechnung der fibonanic Sequenz. Rekursion gedacht werden kann wie ein Baum, so zu berechnen, Fib(8) sagen, dass, durch definition, die wir nehmen, Fib(7) + Fib(6)
```
        Fib(8)
        /    \
    Fib(7)   Fib(6)
```
Die wiederum erfordern-computing-Fib(6), Fib(5), Fib(4) wie folgt:
```
                 Fib(8)
               /        \
          Fib(7)       Fib(6)
        /        \    /      \
     Fib(5)   Fib(6) Fib(5)  Fib(4)
```
Und so weiter. Was Sie tun, produzieren würde, eine andere, Tiefe: 1 Baum:
```
    Fib(8)
    /    \
   7      6
```
Weil, wenn Sie nie rufen Sie die Funktion innerhalb der Funktion, kann es nie gehen mehr in die Tiefe. Es sollte klar sein, aus dieser und den anderen Antworten, warum es nicht richtig ist.

InformationsquelleAutor T. Kiley

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.