Ich habe das obige direkt hier geschrieben, also kann es nicht kompiliert werden, denke aber, dass es funktioniert.
Kann jemand ausführlich erklären, wie das im Sinne funktioniert, wie es gespeichert wird? Es beginnt mit der Berechnung von 5 * (5-1), dann bis zu 4 * (4-1) und dann 3 * (3-1) ..... bis es zu 1 kommt, das nur 1 zurückgibt, richtig? Entschuldigung dafür, so skizzenhaft zu sein, ich wäre nur daran interessiert, herauszufinden, wie das funktioniert genau
Danke
aber wie es funktioniert - es bekommt die Werte für die einzelnen Stufen
5 * (5-1) 4 * (4-1) ... ... ...
Wie werden diese gespeichert und dann zurückgeholt oder fehlt mir etwas?
Stellen Sie sich vor, Sie sind der Computer und jemand reicht Ihnen ein Papier mit
%Vor%darauf geschrieben. Sie führen dann die Prozedur aus und betrachten das Argument. Da es & gt; 1, schreibst du
%Vor%auf ein anderes Stück Papier und "hand es für sich selbst", warten, bis Sie die Antwort auf diese, bevor Sie fortfahren.
Erneut führen Sie die Prozedur aus. Da 2 immer noch & gt; 1 schreibst du
%Vor%auf ein weiteres Stück Papier und geben Sie es sich selbst, warten Sie, bis Sie die Antwort auf dieses eine erhalten, bevor Sie fortfahren.
Auch hier führen Sie die Prozedur aus. Diesmal ist die Eingabe 1, also nimmst du den ersten Zweig und gibst 1 zurück. Der Aufruf, der factorial (2) verarbeitet hat, hat nun eine Antwort, so dass er 2 mit dieser Antwort multipliziert (1) und zurückgibt. Nun erhält der Aufruf, der factorial (3) behandelt hat, seine Antwort (2) und multipliziert ihn mit 3, was 6 ergibt. Er gibt diese Antwort dann an die Person zurück, die die gesamte Operation gestartet hat.
Wenn Sie sich vorstellen, dass Sie die Blätter in einem Stapel vor sich hielten, während Sie arbeiteten, ist das eine Visualisierung des "Stapels" im Speicher des Computers. Jeder rekursive Aufruf speichert den Parameter (und alle temporären Variablen) auf seinem eigenen Blatt Papier (Stapelrahmen), das buchstäblich wie ein Pushdown-Stapel wie die Papiere übereinander angeordnet ist.
Ja, Sie haben es richtig im Code, es prüft zuerst den Wert von n , wenn es kleiner oder gleich 1 ist, das ist der sogenannte -Base-Case . Sie sind wichtig, sie sagen Ihrer rekursiven Funktion, wann sie aufhören sollen.
Wenn der Wert von n nicht kleiner oder gleich ist, wird der Wert von n multipliziert mit dem rekursiven Aufruf von factorial , aber mit dem Wert n-1 zurückgegeben, bis der Basisfall erreicht ist: if (n <= 1) , wo es 1
Ihr Basisfall wurde durch die faktorielle Definition von 0! und 1! festgelegt, die beide gleich 1 sind.
Vielleicht hilft dieses Diagramm, um zu verstehen, wie die Anrufe funktionieren.
%Vor% Dies ist das gleiche wie 5! oder 5 x 4 x 3 x 2 x 1
Hoffe, das hilft.
Fragen Sie, wie Rekursion intern funktioniert? Die einzige Satzantwort ist, dass jeder Thread einen "Aufruf-Stack" hat und jedes Mal, wenn eine Methode aufgerufen wird, ein neuer Eintrag auf diesen Stack geschoben wird, der Informationen darüber enthält, welche Methode aufgerufen wird und was die Argumente sind. Wenn die Methode beendet ist, legt sie ihren Rückgabewert wieder auf den gleichen Stapel und die aufrufende Methode zieht sie zurück. In der Höhe wird Ihr Stack also aussehen wie
faktoriell (1) gerufen von faktorial (2) gerufen von Fakultät (3) von faktorial (4) genannt von faktorial (5)
Der Wikipedia-Artikel auf Anruflisten scheint auf den ersten Blick ziemlich gründlich zu sein.
Der Stapel wird auch aufgeräumt, aber das wird zu langweilig beim Tippen. Im Wesentlichen werden alle Werte in einem Methodenaufruf auf den Stapel geschoben und bei der Rückgabe der Methoden aus dem Stapel entfernt. Dadurch bleiben sie zwischen rekursiven Aufrufen getrennt.
Es ist wichtig zu beachten, dass "Rekursion" in Java (eine prozedurale Sprache) anders funktioniert als in Haskell oder F # (funktionale Sprachen).
Wenn wir in Java Rekursion aufrufen, tun wir dies, indem wir den Ausdrucksbaum evaluieren und jeden Teil davon auflösen, bis wir den Wert jedes Teils des Ausdrucks bestimmen. Wenn wir eine andere Funktion aufrufen müssen, fügen wir an dieser Stelle einen Platzhalter für alle Zwischenwerte ein und beginnen dann, einen neuen Ausdrucksbaum für die neue Funktion zu erstellen.
Im Fall der Rekursion machen wir einen Aufruf an die gleiche Funktion, hoffentlich mit verschiedenen Abschlusswerten, die aufgelöst werden müssen, bevor wir die Auswertung des aktuellen Ausdrucks abschließen können. Diese Erweiterungen werden wiederholt aneinandergekettet, bis eines von zwei Dingen eintritt. 1) Wir erreichen einen abschließenden Ausdruck, der die Kontrolle an den Aufrufer zurückgibt (der erste Teil von if in diesem Fall), oder wir verbrauchen unsere Fähigkeit, Zwischenwerte im Speicher und wir zu platzieren Gibt eine Ausnahme zurück (Stack overflow).
Im ersten Fall beginnen wir dann, jeden der Ausdrucksbäume vom Anfang des Stapels aufzulösen, indem wir uns nach hinten arbeiten, bis keine Stapeleinträge mehr übrig sind. An diesem Punkt wird der Ausdrucksbaum in den zurückgegebenen Endwert aufgelöst.
Jims Antwort ist eine ausgezeichnete physikalische Metapher dafür.
Es ist schwer zu erraten, mit welchem Teil der Rekursion Sie Schwierigkeiten haben, aber ich werde diesen Teil Ihrer Frage hinterfragen:
bis es zu 1 kommt, die nur 1 zurückgeben wird, richtig?
Ich vermute, Sie meinen, "wenn es nur 1 zurückgibt, warum ist das Ergebnis der Funktion nicht 1?"
Wenn Sie von einer Funktion (in diesem Fall factorial) zurückkehren, geben Sie einen Wert an denjenigen zurück, der ursprünglich danach gefragt hat.
Wenn ich sage " gib mir faktoriell (5) ", dann wird factorial (5) mir einen Wert zurückgeben, aber bevor er mir den Wert zurückgeben kann, muss er factorial (4) fragen Wert, faktoriell (5) sagt im Wesentlichen " gib mir faktoriell (4), also kann ich es mit 5 multiplizieren und es dem Typen zurückgeben, der nach Fakultät (5) fragte ." Nun wird factorial (4) seinen Wert auf factorial (5) zurückgeben, was es mit n multiplizieren und seinen Wert an mich zurückgeben kann. Erinnere dich, ich habe nicht nach dem Wert des Faktors (4) gefragt, es ist mir auch egal, und es kam nicht zu mir zurück, es ging zurück auf faktoriell (5).
Wenn Sie faktoriell (1) drücken, haben Sie faktorielle (2), faktorielle (3), faktorielle (4) und faktorielle (5), die alle darauf warten, eine Antwort zurück zu bekommen. Factorial (1) wird seinen Wert (der aufgrund Ihres Basisfalls 1 ist) an factorial (2) zurückgeben, der schließlich zu factorial (3) usw. zurückkehren kann. An diesem Punkt wird die Rekursion abgeschlossen und Sie werden es tun Erhalte den Wert von factorial (5) zurück.
Ein praktischer Ansatz, der eine gute IDE erfordert (Eclipse, Netbeans, IntelliJ):
Fügen Sie der Zeile, die return 1 liest, einen Haltepunkt hinzu und debuggen Sie die Anwendung. Wenn es aufhört, schauen Sie sich die Stack-Trace an. Sie werden sehen, dass die faktorielle Methode mehrmals aufgerufen wurde.
Die Eclipse-Debug-Ansicht zeigt den suspendierten Thread und einen Stack mit sechs Einträgen, wobei jede Zeile eine Codezeile darstellt, an der eine andere Methode aufgerufen wird (mit Ausnahme des obersten Eintrags - das ist der Breakpoint). faktoriell erscheint fünf Mal, Sie können jede Zeile auswählen und den Wert von n in der Variablenansicht sehen (dies ist grundlegend und sollte auf die andere IDE in ähnlicher Weise funktionieren).
Das sollte eine weitere Idee geben, wie rekursive Methodenaufrufe funktionieren (und warum Sie einen Speichermangelfehler erhalten, wenn Sie die Ausstiegskriterien nicht richtig definieren;))