Wie funktioniert eine Rekursionsmethode?

Question

Ich fand dieses Beispiel der Rekursion online, aber ich verstehe nicht, was darin passiert.

public class MysteryClass { 
    public static void mystery(int n) { 
     if (n > 0) { 
      mystery(n-1); 
      System.out.println(n * 4); 
      mystery(n-1); 
     } 
    } 
    public static void main(String[] args) { 
     MysteryClass.mystery(2); 
    } 
} 

die Ausgabe

4 
8 
4 

Was ich verstehe, ist, dass

1. 2 ist größer als 0
2. 2 - 1 = 1
3. 1 ist größer als 0
4. 1 - 1 = 0
5. 0 ist nicht größer als 0
6. Jetzt sind wir zu dieser Zeile springen: System.out.println(n * 4);
7. 1 * 4 = 4
8. 2 * 4 = 8
9. Hier verstehe ich nicht, warum ich noch ein „4 erhalten Ausgabe

Was passiert in Schritt 9?

Ich habe einen Debugger aber immer noch nicht verstanden.

Answer 1

MysteryClass.mystery(2); 
    if (2 > 0) (true) ---> mystery(2-1); 
    | if(1 > 0) (true) ---> mystery (1-1); // Action (A) 
    | | if(0 > 0) (false) ---> // do nothing 
    | |  
    | System.out.println(1 * 4); 
    | mystery(1-1); 
    | 
    System.out.println(2 * 4); 
    mystery(2-1); ---> // repeat action (A) 

Answer 2

Wenn Sie Ihren n mit 2 ersetzen, sehen Sie exacly:

if (2 > 0) { 
    mystery(2-1); // prints 4 
    System.out.println(2 * 4); 
    mystery(2-1); // prints 4 
} 

Sie haben zwei Gespräche mit mystery(2-1); One vor und eine nach der System.out.println

Da alle mystery(2-1); 4 von Druck führen , also das Ergebnis 4 8 4

Answer 3

Wenn Sie diesen Code ausführen mit n=2

mystery(n-1); 
    System.out.println(n * 4); 
    mystery(n-1); 

Es bedeutet, dass es zweimal mysteriös (1) läuft. Zuerst wird das Mysterium (1) ausgeführt, das die Ausgabe 4 erhält, aber die nächste zwei Rekursion mit Mysterium (0) endet in der Ader. Daher geht es weiter zu

System.out.println(n * 4); 

Welche 8

Dann läuft es Geheimnis (1) noch einmal die 4. druckt

Answer 4

hier verstehe ich nicht, warum ich noch einmal bekommen 4 als Ausgabe was passiert in Schritt 9 ???

Weil n nicht geändert wird. So werden Sie es noch einmal mit mystery(2-1);

Answer 5

ausführen Sie tun eine doppelte Rekursion - die gleiche Funktion wird ZWEIMAL genannt. Dein Ausführungspfad ist also falsch.Beachten Sie die folgende Änderung für Klarheit:

mystery(n-1); // pretend this is function "A" 
    System.out.println(n * 4); 
    mystery(n-1); // pretend this is function "B" 

1. Geheimnis (2) // die Rekursion starten
2. A (2-1) -> A (1) // n> 0, so nennen A (
)
3. A (1-1) -> A (0) // n == 0, so geschieht nichts
4. Rückkehr aus (3)
5. println (1 * 4) -> 4
6. return von (2)
7. println (n * 4) -> println (2 * 4) -> 8
8. B (2-1) -> B (1) // wir sind zurück zum ursprünglichen (1) Aufruf des Geheimnisses
9. A (1- 0) -> A (0) // etc ...

Answer 6

zu verstehen, um Rätsel ersetzen (n-1) in Geheimnis zu kodieren:

int n1 = 2 
if (n1 > 0){ // step 1 
    int n2 = n1 - 1; // step2: 1 
    if (n2 > 0){ // step 3 
     int n3 = n2 - 1; // step4: 0 
     if (n3 > 0){ // step 5: false 
     ... 
     } 
     System.out.println(n2 * 4); // step 6: print 4 
     int n3_1 = n2 - 1; // step 7: 0 
     if (n3_1 > 0){ // false 
     ... 
     } 
    } 

    System.out.println(n1 * 4); // step 8: print 8 

    if (n2 > 0){ 
     int n3 = n2 - 1; // 0 
     if (n3 > 0){ // false 
     ... 
     } 
     System.out.println(n2 * 4); // step 9: print 4 
     int n3_1 = n2 - 1; // 0 
     if (n3_1 > 0){ // false 
     ... 
     } 
    } 

} 
} 

Answer 7

ich nur Rekursion verstehen kann Ich denke darüber nach, was passieren würde, wenn ich den gesamten Code kopieren und einfügen würde, damit alles an der gleichen Stelle ist.

Sie mystery(2) mit den drei Linien

mystery(1); 
System.out.println(8); 
mystery(1); 

Deshalb

public static void main(String[] args) { 
    mystery(1); 
    System.out.println(8); 
    mystery(1); 
} 

genauso gut sagen, dass Ihre main Methode könnte ersetzen können Sie sowohl dieser mystery(1); Anrufe von

mystery(0); 
System.out.println(4); 
mystery(0); 

ersetzen

Das bedeutet, dass die main Methode könnte auch einfach sagen

public static void main(String[] args) { 
    mystery(0); 
    System.out.println(4); 
    mystery(0); 
    System.out.println(8); 
    mystery(0); 
    System.out.println(4); 
    mystery(0); 
} 

mystery(0); nichts effektiv der Fall ist, so könnte main gerade auch

public static void main(String[] args) { 
    System.out.println(4); 
    System.out.println(8); 
    System.out.println(4); 
}