Java Rekursion: Beispiel
Ich bin mir bewusst, wie Rekursion funktioniert, ich.e:
method calls itself until it reaches a base case then it can start solving its problem.
In diesem code-Beispiel wird eine Methode oder entfernen von Blumen aus einer vase.
Ich habe eine trace-Anweisung, um in der Lage sein zu sehen, wie viele Blumen sind in der vase nach jedem Aufruf. Jedoch ist die output-Blätter, 7 Blüten in der vase. Ich bin verwirrt, warum?
Code:
public static void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
//take one flower and
emptyVase( flowersInVase - 1 ) ;
System.out.println(flowersInVase);
} else {
//the vase is empty, nothing to do
}
}
Aufrufen der Methode:
public class RecursionPractice {
public static void main(String[] args) {
emptyVase(7);
}
Ausgabe:
1
2
3
4
5
6
7
- Java übergibt Argumente Call-by-Value.
- was meinst du?
- Sie müssen übergeben Sie die variable flowersInVase durch Verweis auf die änderungen
- In einfachen Worten: niemand wird je sehen, was
emptyVase()
hat zuflowersInVase
. - Danke, bitte Lesen Sie meine Frage bearbeitet
- Sind Sie jetzt unter Bezugnahme auf die Reihenfolge der Drucke? Wenn dies ist ein Anliegen swap-System.aus.println() und emptyVase() Zeile.
- Ich bin im Grunde Fragen, warum die vase nicht leer ist, am Ende des Gesprächs?
Du musst angemeldet sein, um einen Kommentar abzugeben.
In der Rekursion die Reihenfolge der Aufrufe ist wichtig!!! Können Sie besser verstehen, Ihre eigenen Beispiel, wenn Sie entrollen es. Es wird wie folgt Aussehen:
Nun die stack sieht wie folgt aus:
In stack frame für
emptyVase(1)
die Ausführung der Funktion erfolgt, so drucken Sie die aktuelleflowerInVase
die 1. Gehen Sie zurück zur vorherigen stack frame, jeder Zeit drucken die aktuell gespeicherten Variablen, bis die letzten stack frame erreicht ist.... Und das ist der Grund, warum die Reihenfolge wird Umgekehrt! Das ist auch der Grund, warum, wenn Sie die Reihenfolge ändern, der Druck und die Ausführung der Funktion wird es Aussehen, als erwartet.
Ergeben:
Den vase ist eigentlich leer, aber da Ihr Zustand ist
flowerInVase > 0
, das heißt, wenn das Letzte nennen ist mitemptyVase(0)
die sonst Teil genommen wird und man nicht drucken, da der Wert des Zählers. Hinzufügen drucken Sie es und Sie werden sehen, eine leere vase.Ihrem Ansatz (und dem Beispiel) zum Verständnis der Rekursion ist gut. Ich denke, die wichtigste Sache zu bemerken in Ihrem Beispiel ist die Tatsache, dass der rekursive Aufruf unterbricht die aktuelle Funktion Anruf und startet einen neuen (führt die gleiche Funktion wieder), aber der Vorherige Anruf ist erinnert und sobald der neue Aufruf erfolgt ist, die flow fortgesetzt, wo es unterbrochen wurde!
Könnte man sich vorstellen, jeder rekursiven Aufruf als eine Schaffung von box in einer box:
Den tiefer die Rekursion, desto mehr Kisten Sie haben.
Dies ist auch, wo das problem ist. Rekursion ist ganz schön teuer in Bezug auf die Zuweisung von Speicher und weil die Computer haben eine begrenzte Menge an Speicher, wenn die Rekursion erzeugt zu viele Boxen, die Ausführung des Programms erreicht die maximal zulässige Anzahl der Kartons = stack-frames und sagt stack overflow. Sich bewusst sein, dass meine Erklärung ist eine sehr einfache. Für eine ausführliche Erklärung der sogenannten call-stack haben Sie einen Blick auf diese Wikipedia-Artikel - Call-stack.
Jedem Aufruf
emptyVase()
druckt eineflowersInVase
Wert , also im Grunde werden Sie rufenSystem.out.println()
7 mal. Die erste print - '1' ist für den letzten Anruf zuemptyVase()
, die zweite '2' ist für die vor Letzte und so wieder .Der Letzte '7' steht für den ersten AufrufemptyVase()
Hexe war wirklich 7 Blume in der vase.Nopes. Die Methode ist gut. Es wird auf die Beseitigung einer Blume aus der vase, bis die vase leer ist. Wenn Sie erwarten, dass die unten Ausgabe(unter der Annahme, dass die Methode aufgerufen wird, mit
flowersInVase
10 ):10
9
8
7
6
5
4
3
2
1
Dann sollten Sie schreiben
System.out.println(flowersInVase); emptyVase( flowersInVase - 1 );
stattemptyVase( flowersInVase - 1 ); System.out.println(flowersInVase);
versuchen Sie es mit einem int[] anstatt (nur kopieren und einfügen den code und substituiert das array für int-Sie müssen zu überprüfen, ob dies funktioniert)
...
Der Grund, warum es nicht mit einem primitiven
int
ist, da nur das Wert der int übergeben wird, nicht eine Referenz auf die Speicheradresse den Wert, die ist, was Sie brauchen, um die Veränderung spiegelt sich in allen Methodenaufrufen.