Verstehe Rekursion nicht ganz

[Käsekuchen]

public class Baum {
    private Knoten start;
    
    //Baum erstellen
    public void einfuegen(Knoten neu) {
        if(start == null) {
            start = neu;
        }
        else {
            einfuegen(start,neu);
        }
    }
    public void einfuegen(Knoten temp, Knoten neu) {
        if(neu.getAlter()<temp.getAlter()) {
            if(temp.left==null) temp.left = neu;
            else einfuegen(temp.left,neu);
        }
        if(neu.getAlter()>temp.getAlter()) {
            if(temp.right==null) temp.right = neu;
            else einfuegen(temp.right,neu);
        }
    }
    
    //Baum ausgeben
    public void ausgeben() {
        ausgeben(start);
    }
    
    public void ausgeben(Knoten temp) {
        if(temp == null) return;
        
        if(temp.left!=null) ausgeben(temp.left);
        
        System.out.println(temp.getAlter());
        
        if(temp.right!=null) ausgeben(temp.right);
        
    }
        public static void main(String[]args) {
        Baum xxx = new Baum();
        Knoten eins = new Knoten("Jakob",23);
        Knoten zwei = new Knoten("Jonas",24);
        Knoten drei = new Knoten("Eva",26);
        Knoten vier = new Knoten("Peter",28);
        
        xxx.einfuegen(eins);
        xxx.einfuegen(zwei);
        xxx.einfuegen(drei);
        xxx.einfuegen(vier);
        
        
       
        System.out.println();
        
    }
}

public class Knoten {
    private String name;
    private int alter;
    
    Knoten left;
    Knoten right;
    
    public Knoten(String name, int alter) {
        this.name=name;
        this.alter=alter;
    }
    
    public String getName() {
        return name;
    }
    public int getAlter() {
        return alter;
    }
}

Ich bräuchte mal eure Hilfe, irgendwie hab ich Rekursion nich so wirklich verstanden. Die Frage bezieht sich auf die ausgeben() Methode. Ich versteh einfach nicht, was da genau passiert. Für mich ist es so weit verständlich, dass wir im Baum immer weiter runter gehen bis eben System.out.println(temp.getAlter()); ausgeführt wird. Aber wie kommt es zustande, dass die anderen werte auch ausgegeben werden ?

 

[Blender3D]

Aber wie kommt es zustande, dass die anderen werte auch ausgegeben werden ?

Der Aufruf der Methode ausgeben( Knoten ) wird im Funktion Stack gespeichert.
Start.......=.... 17
......................./.....\
...................12......13
.................../
................15
ausgeben( 17 ) -> ausgeben( 12 ) -> ausgeben ( 15) -> ausgeben(13)
Ausgabe:
15
12
17
13

 

[mihe7]

Ich versteh einfach nicht, was da genau passiert.

Tatsächlich passiert da nichts besonderes: es wird eine Methode aufgerufen, das ist alles. Dass es sich dabei um die gleiche Methode handelt, in der man sich gerade befindet, macht erstmal keinen Unterschied.

D. h. Du kannst die Methodenaufrufe zunächst einmal wie eine Black-Box behandeln, wir können sie einfach mal ersetzen:

    public void ausgeben(Knoten temp) {
        if(temp == null) return;
        
        if(temp.left!=null) x(temp.left);
        
        System.out.println(temp.getAlter());
        
        if(temp.right!=null) x(temp.right);        
    }

Was also passiert nun in der Methode? Wenn temp null ist, wird die Methode sofort beendet. Wenn temp.left != null gilt, wird eine Methode (hier x) aufgerufen, dabei wird temp.left als Argument übergeben. Nun endet der Aufruf von x irgendwann auch wieder und im Anschluss wird das Alter von temp ausgegeben. Danach wird geprüft, ob right != null ist. In dem Fall wird nochmal eine Methode (hier x) aufgerufen, dabei wird temp.right als Argument übergeben. Wenn der Aufruf von x endet, sind wir am Ende der Methode ausgeben angelangt und die Methode endet. Das war es auch schon.

Jetzt kannst Du x wieder durch ausgeben ersetzen und den Spaß genau so nachvollziehen. Wenn Du also den Baum von @Blender3D nimmst, dann kannst Du schon einmal sagen: ok, es wird ausgeben(12) ausfgerufen, danach wird die 17 ausgegeben, danach wird ausgeben(13) aufgerufen.

ausgeben(12)
17
ausgeben(13)

Was passiert bei ausgeben(12)? Naja, das gleiche wieder: es wird ausgeben(15) aufgerufen, es wird die 12 ausgegeben, danach passiert nichts weiter, da 12 keinen rechten Kindknoten besitzt.

ausgeben(15)
12
17
ausgeben(13)

Was passiert bei ausgeben(15)? Es gibt weder einen linken noch einen rechten Kindknoten, also wird nur die 15 ausgegeben:

15
12
17
ausgeben(13)

Bleibt noch ausgeben(13)... Hier gilt das gleiche wie gerade eben: kein linker, kein rechter Kindknoten, nur die 13 wird ausgegeben:

15
12
17
13

Fertig.

 

[White_Fox]

Mal zum allgemeinen Verständnis:

Rekursion – Wikipedia

de.wikipedia.org

Das Bild in dem Artikel verdeutlicht das eigentlich perfekt, auch wenn es kein Quellcode ist.

Rekursion ist auch eine Problemlösungsstrategie. Komplexe Sachverhalte können oft mit rekursiv formulierten Regeln sehr elegant erfasst werden. Das Grundprinzip ist dabei dann das Zurückführen einer allgemeinen Aufgabe auf eine einfachere Aufgabe derselben Klasse. Das wird u. a. auch beim sogenannten rekursiven Programmieren genutzt: Um Rekursion entstehen zu lassen, muss eine Prozedur, Funktion oder Methode lediglich sich selbst aufrufen. Dieser Prozess läuft weiter, bis eine im Programm enthaltene Abbruchbedingung greift.

 

[Käsekuchen]

Tatsächlich passiert da nichts besonderes: es wird eine Methode aufgerufen, das ist alles. Dass es sich dabei um die gleiche Methode handelt, in der man sich gerade befindet, macht erstmal keinen Unterschied.

D. h. Du kannst die Methodenaufrufe zunächst einmal wie eine Black-Box behandeln, wir können sie einfach mal ersetzen:

    public void ausgeben(Knoten temp) {
        if(temp == null) return;
       
        if(temp.left!=null) x(temp.left);
       
        System.out.println(temp.getAlter());
       
        if(temp.right!=null) x(temp.right);       
    }

Was also passiert nun in der Methode? Wenn temp null ist, wird die Methode sofort beendet. Wenn temp.left != null gilt, wird eine Methode (hier x) aufgerufen, dabei wird temp.left als Argument übergeben. Nun endet der Aufruf von x irgendwann auch wieder und im Anschluss wird das Alter von temp ausgegeben. Danach wird geprüft, ob right != null ist. In dem Fall wird nochmal eine Methode (hier x) aufgerufen, dabei wird temp.right als Argument übergeben. Wenn der Aufruf von x endet, sind wir am Ende der Methode ausgeben angelangt und die Methode endet. Das war es auch schon.

Jetzt kannst Du x wieder durch ausgeben ersetzen und den Spaß genau so nachvollziehen. Wenn Du also den Baum von @Blender3D nimmst, dann kannst Du schon einmal sagen: ok, es wird ausgeben(12) ausfgerufen, danach wird die 17 ausgegeben, danach wird ausgeben(13) aufgerufen.

ausgeben(12)
17
ausgeben(13)

Was passiert bei ausgeben(12)? Naja, das gleiche wieder: es wird ausgeben(15) aufgerufen, es wird die 12 ausgegeben, danach passiert nichts weiter, da 12 keinen rechten Kindknoten besitzt.

ausgeben(15)
12
17
ausgeben(13)

Was passiert bei ausgeben(15)? Es gibt weder einen linken noch einen rechten Kindknoten, also wird nur die 15 ausgegeben:

15
12
17
ausgeben(13)

Bleibt noch ausgeben(13)... Hier gilt das gleiche wie gerade eben: kein linker, kein rechter Kindknoten, nur die 13 wird ausgegeben:

15
12
17
13

Fertig.

Ich versteh irgendwie nur, wie es zur ersten Ausgabe kommt. Wenn ich bei System.out.println(temp.getAlter()); bin, dann wird mir das Alter ausgegeben. Dann ist die Methode doch vorbei. Warum werden aber alle Zahlen ausgegeben und nicht nur eine

 

[Jw456]

Du bist ja den Baum von oben nach unten Links durch gegangen . Und hast mehrere habfertige Methoden auf dem Stack liegen.
Die jetzt nun weiter abgearbeitet werden. Bis wirklich alle Methoden ferig bearbeit wurden.

 

[White_Fox]

Mal ein einfacheres Beispiel, vielleicht findest du das Muster in deinem großen Code ja wieder. Nimm mal diese Methode:

/*
 *Zählt runter bis auf 0
 */
public int countDown(int i){
    if(i >= 0){}
        System.out.println(countDown(i - 1));
    }
    return start;
}

Prinzipiell solltest du diese Methode jetzt einfach mit einem int, z.B. 3, füttern und es die Ausgabe
3
2
1
0
auf dem Bildschirm erscheinen. Gut möglich daß da ein paar Fehlerchen sind wie daß die Null zum Schluß doppelt ausgegeben wird, aber darum geht es erstmal nicht.
Was in der Methode passiert, ist daß sie sich fortwährend selbst aufruft, sofern der Parameter i größer oder gleich null ist, sonst wird einfach der Parameter zurückgegeben. Das ist, was Jw456 mit "halbfertigen Methoden auf dem Stack" meinte, die Methode ruft sich erstmal so oft auf wie benötigt, und dann liefern die vielen Aufrufe ihr jeweiliges Ergebnis zurück. Sieht dann so aus:



In deinem Code fängst du links beim oberen Pfeil an mit einem einzigen Methodenaufruf:

//Rufe die Methode countDown(i) auf, entspricht dem oberen linken Pfeil im Bild...
countDown(3);
//...und hier bist du schon fertig, d.h. der untere Pfeil auf der linken Seite.

Damit erschlägst du ein Problem in einem Einzeiler, brauchst keine Schleife, keine Zählvariable oder dergleichen, sondern einfach nur ein bischen Platz im Speicher.

 

[mihe7]

Wenn ich bei System.out.println(temp.getAlter()); bin, dann wird mir das Alter ausgegeben. Dann ist die Methode doch vorbei.

Du verwechselst Methode und Ausführung der Methode im Rahmen eines Methodenaufrufs. Es endet nicht die Methode, sondern nur die Ausführung eines konkreten Aufrufs. Diese Aufrufe können verschachtelt sein.