Fibonacci-Zahlen, warum funktioniert diese wiederkehrende Funktion?

Question

Ich gehe durch ein Programmierbuch und eines der Beispiele ist über Fibonacci-Zahlen, und wie eine wiederkehrende Funktion findet die Fibonacci-Nummer für die n-te entlang.

Der Code sieht wie folgt aus:

Int fib (int n) 
{ 
If (n<3) 
Return (1); 
Else 
Return (fib(n-1))+(fib(n-2)) 
} 

Nun ist diese nicht exakt ist, weil ich von meinem Handy tippen bin, und ich habe Verständnis, wie der Code funktioniert, es ruft sich selbst, bis es 1 zurückkehrt, dann addiert es die Rückgabewerte, bis Sie die korrekte Fibonacci-Nummer für die Position in der Sequenz haben.

So brauche ich keine Hilfe mit dem Code. Was ich brauche, ist zu verstehen, warum das funktioniert. Wie liefert das Hinzufügen aller Rückgaben die richtige Antwort?

Bitte kann jemand erklären, warum das funktioniert. Vielen Dank. Es treibt mich in den Wahnsinn.

Answer 1

Eine Fibonacci-Zahl ist definiert als die Summe der beiden vorhergehenden Fibonacci-Zahlen. Das gibt die folgenden:

1 1 2 3 5 8 13 ... 

Also für die dritte Zahl (1 1) das Ergebnis nehmen würde die vorherige finden - dh 2. (1 2) Anzahl und fügen Sie es an die Nummer vor dem vorherigen - dh 1. (1 2) Nummer.

Sie müssen auch verstehen, dass das Programm den Wert der beiden vorhergehenden Zahlen berechnen muss, bevor es die Zahl berechnen kann, die Sie wissen möchten. Deshalb nennt es sich immer selbst - mit der gleichen Methode - bis es alles berechnet hat.

Answer 2

Eine Fibonacci-Nummer ist definiert als die Summe der beiden vorherigen Fibonacci-Zahlen. Diese sind jeweils definiert als die Summe der beiden vorherigen Fibonacci-Zahlen. Etcetera, und so weiter, bis du 1 erreichst. Jede zufällige Fibonacci-Zahl kann als die Summe zweier Fibonacci-Zahlen definiert werden; diese können rekursiv als die Summe von zwei Fibonacci-Zahlen usw. definiert werden. Das heißt, die Definition einer Fibonacci-Zahl ist grundlegend rekursiv; Das heißt, die Definition beinhaltet, was es definiert.

Dieses Zeug kann schwierig sein, aber es ist sehr grundlegend für das Verständnis von Rekursion und Informatik. Mach weiter daran; Es wird irgendwann klicken.

Answer 3

Es recursion genannt

Answer 4

würde ich vorschlagen, wie Rekursion Werke zu verstehen. Grundsätzlich FIB-Funktion ausgeführt wird selbst mit einem kleineren Argument bis Argument auf 2 kommt, dann kehrt gerade 1.

fib(1) = 1 
fib(2) = 1 
fib(3) = fib(2) + fib(1) = 1 + 1 = 2 
fib(4) = fib(3) [ fib(2) + fib(1) = 1 + 1 = 2 ] + fib(2) = 2 + 1 
... 

Ein Weg, um zu verstehen, wie es funktioniert, ist es in einem Debugger Schritt-für-Schritt auszuführen.

Answer 5

Rekursion ist wie folgt aus:

1. Ein Kind kann nicht schlafen, so ihre Mutter erzählte ihr eine Geschichte über einen kleinen Frosch,
2. , die nicht schlafen konnte, so der Frosch Mutter erzählte ihr eine Geschichte über einen kleinen Bären,
3. , die nicht schlafen konnte, so die Mutter Bär ihr eine Geschichte über einen kleine Wiesel erzählt ...
4. wer schlief ein.
5. ..und der kleine Bär schlief ein;
6. ... und der kleine Frosch schlief ein;
7. ... und das Kind schlief ein.

source

Answer 6

Per Definition sind Fibonacci-Zahlen die Summe der beiden vorhergehenden Zahlen in der Serie (wobei die ersten beiden sind 0 und 1).

Wenn Sie also die Fibonacci-Nummer an einer Stelle erhalten, können Sie sie als Summe der beiden früheren Fibonacci-Nummern neu schreiben.

Mit Rekursion gehen Sie durch diesen Prozess, bis die "zuvor zwei Fibonacci-Nummern" sind 1 und 1 (im Falle dieses Algorithmus), und fahren Sie dann fort, die Zahlen addieren "Sichern" die Rekursion bis Sie Gehe zurück zu deinem ursprünglichen Ort in der Reihenfolge.

Answer 7

Es ist die Definition von Fibonacci-Zahlen.

Die n-te Fibonacci-Zahl gibt die Summe der (n-1) ten und (n-2) -ten Fibonacci-Zahlen zurück.

So können wir durch induktive Argumentation beweisen, dass, wenn fib (n-1) und fib (n-2) die gültige (n-1) -te und (n-2) -te Fibonacci-Zahl, fib (n) = fib (n-1) + fib (n-2) ist die gültige n-te Fibonacci-Zahl.

Der Basis Schritt ist, dass FIB (1) und FIB (2) korrekt sind (das ist fib es (1) = FIB (2) = 1), ...

Answer 8

Der Trick, um das Verständnis der Rekursion ist das Verständnis der Stapel.

ich auf Linie bin 2 in einer Funktion namens main, alle meine lokalen Variablen in meinem Stack-Frame gespeichert sind:

+------------------+ 
| main() variables | The stack frame 
+------------------+ 

ich dann fib(3) nennen, damit der Computer meine aktuelle Position schiebt (EIP) zu Der Stack erstellt dann einen neuen Stack-Frame für fib und fügt diesen hinzu. Ich kann immer nur den oberen Stapelrahmen zuzugreifen:

+------------------+ 
| fib() n = 5  | Top of stack (current frame) 
+------------------+ 
| EIP: main @ 2,1 | 
+------------------+ 
| main() variables | Bottom of stack 
+------------------+ 

Zeile 4 von fib, ruft fib wieder, so dass das gleiche wieder passiert:

+------------------+ 
| fib() n = 4 | Top of stack 
+------------------+ 
| EIP: fib @ 4,1 | 
+------------------+ 
| fib() n = 5 | 
+------------------+ 
| EIP: main @ 2,1 | 
+------------------+ 
| main() variables | Bottom of stack 
+------------------+ 

Und es tut dies immer wieder als die Funktion wird rekursiv aufgerufen. Der Stapel wächst, bis etwas zurückkehrt. An diesem Punkt wird in Zeile 2 von fib 1 zurückgegeben.Daraufhin wird das obere Stapelrahmen und verwirft sie, gibt sie dann die Ausführung an die Ausführungszeiger gespeichert, und das Programm läuft weiter, wo es

links

+------------------+ 
| fib() n = 3 | Top of stack 
+------------------+ 
    ... etc ... 
+------------------+ 
| EIP: main @ 2,1 | 
+------------------+ 
| main() variables | Bottom of stack 
+------------------+ 

Schließlich landen Sie wieder in die aufrufende Funktion aus (oder Sie erhalten einen Stapelüberlauf wie es zu groß wird). Das Wichtigste ist, dass jedes Mal, wenn die Funktion aufgerufen wird, ein neuer Stack-Frame mit all Ihren lokalen Variablen abgerufen wird und Ihre vorherige Position gespeichert wird. Das ist Rekursion.

Das Hauptproblem ist, dass im Unterricht Menschen Rekursion, jeder immer die Fibonacci-Sequenz verwendet, was bedeutet, zwei rekursive Funktionsaufrufe auf einer Zeile. Das ist unnötig verwirrend, da Sie mir sicher zustimmen werden!

Answer 9

sollte dieses Video-Tutorial Ihnen ein besseres Bild davon, wie Fibonacci Rekursion arbeitet

[link] http://www.schooltrainer.com/study-material/computer-science/stepping-through-recursive-fibonacci-function.html