Rekursive Methode - Verständnisproblem

[Cryver]

Einen schönen guten Tag zusammen,

ich hab die Suche und Google verwendet, in der Hoffnung, zu diesem Thema eine für mich verständliche Antwort zu finden- leider war dem nicht so.

Ich beschäftige mich seit einigen Tagen mit Java und lese hierzu ein Buch (bzw. E-Book). Da ich jetzt nicht weiß, inwiefern es Werbung ist, lasse ich den Namen weg, reiche Ihn aber, wenn gewünscht, gerne nach.

Nun kam ich am Samstag auf das Thema "Rekursive Methode".

Ich komme soweit klar, bis ich als Beispiel einen solchen Code (Anmerkung: Ich verwende den NetBeans Editor, der mir von einem Bekannten empfohlen wurde; Version 7.0.1) sehe:

package rekursiondemo;


public class RekursionDemo {


    static void move( int n, String fromPeg, String toPeg, String usingPeg )

    {

        if (n > 1)

        {   

            move(n-1,fromPeg,usingPeg,toPeg);

            System.out.println("Bewege Scheibe " + n + " von der " + fromPeg + " zur " + toPeg + ".");

            move(n-1,usingPeg,toPeg,fromPeg);

        }

        else

        {

            System.out.println("Bewege Scheibe " + n + " von der " + fromPeg + " zur " + toPeg + ".");

        }

    }



    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) 

    {

        // TODO code application logic here

        move(3,"Kupfersäule","Goldsäule","Silbersäule");

    }

}

Dieses Beispiel ist aus dem oben genannten E-Book.

Ich verstehe, dass eine rekursive Methode nichts anderes ist, als eine Methode, die sich bis zur Abbruch Bedingung immer wieder selbst aufruft.

Aber, was ich einfach nicht verstehe, ist, wie genau der Vorgang läuft- spezifisch auf dieses Beispiel gemünzt.

Die ersten 3 Zeilen, die ausgegeben werden, krieg ich so auf dem Papier hin- bei den folgenden Ergebnissen verfehle ich total.

n-1: 3 fromPeg: Kupfersäule toPeg: Goldsäule usingPeg: Silbersäule

n-1: 2 fromPeg: Kupfersäule toPeg: Silbersäule usingPeg: Goldsäule

n-1: 1 fromPeg: Kupfersäule toPeg: Goldsäule usingPeg: Silbersäule

// Bis hierhin mach ich auf dem Papier alles richtig //

Das ist das Ergebnis, wie es weitergehen würde:

n-1: 1 fromPeg: Goldsäule toPeg: Silbersäule usingPeg: Kupfersäule

n-1: 2 fromPeg: Silbersäule toPeg: Goldsäule usingPeg: Kupfersäule

n-1: 1 fromPeg: Silbersäule toPeg: Kupfersäule usingPeg: Goldsäule

n-1: 1 fromPeg: Kupfersäule toPeg: Goldsäule usingPeg: Silbersäule

Ich würde mich sehr freuen, wenn mir jemand auf irgendeine Art und Weise helfen könnte.

Mit freundlichen Grüßen,

Cryv

[flashpixx]

Ich tippe mal es handelt sich um Türme von Hanoi und den Randoffscher Algorithmus

Schau Dir die Erklärung zu dem Algorithmus an

[Cryver]

Stimmt, in dem Buch steht dieses Beispiel unter dem Titel.

Was ich allerdings nicht verstehe (zugegeben, da hab ich mich unklar ausgedrückt, entschuldige), wann genau wird der zweite Aufruf von "move()" ausgeführt? Ich vermute, daran scheitert es bei mir.

Nach meinem Verständnis eines Programmablaufs, geht er zum ersten Aufruf von move(), fängt von vorne an und so geht´s dann weiter. Aber irgendwann kommt auch der zweite Aufruf- nur, wann kommt er?

[flashpixx]

Als Tip zum überlegen: Jeder Funktionsaufruf ist wie ein Klammerpaar move(), d.h. wenn ich zwei zwei Rekursionen habe sieht es so aus move( move() ). Natürlich können noch mehrere Befehle vor / nach dem move folgen also z.B. move( do(a) move( do(a) do( ) do( ). Schau Dir Deinen Code an und überlege Dir, wie die Aufrufe Deiner Funktion verschachtelt sind und wann entsprechend Deine Ausgabe erfolgt.

[baphomet]

Bezüglich der Rekursion hättest du asl Einsieg ein einfacheres Beispiel nehmen können, etwa die Berechnung von Fibonacci-Zahlen, oder noch einfacher Fakultät und dann hättest die Funktionsweise auch verstanden.

Hier mal nen kleiner Code

long Fakultaet(int Zahl) {

     if(zahl==0 || zahl==1) return 1;

     else return Fakultaet(zahl-1)*zahl;

}

Sollte doch klar sein oder, wenn man 0 oder 1 übergeben werden wird einfach 1 zurückgegeben, anderenfalls wir Rekursion angewendet.

Spielen wirs mal für 3 durch, es wird die Fakultaetsfunktion nochmals mit dem Parameter zwei aufgerufen und nochmals Rekursion angewendet

mit der Übergabe von 1, damit endet die Rekursion.

Letztendlich ist es aber besser sowas per Iteration zu lösen.

[Cryver]

@baphomet: Soweit hab ich rekursive Funktionen verstanden, dass ist für mich alles noch ganz verständlich gewesen. Aber danke dir für deine Mühe

Das Problem, wo ich einfach nicht hinter komme (und ich bin bei sowas sehr ehrgeizig) ist das Verständnis von diesen "Türmen von Hanoi". Ich hab mir den Tipp von flashpixx gestern durch den Kopf gehen lassen, hab nu von 8 Uhr an darüber gegrübelt und bin alles durchgegangen, aber ich krieg es einfach nicht hin.

HIer einfach mal mein Gedankengang, wie er generell anfängt.

Beginn:

Die Methode „move( int n, String fromPeg, String toPeg, String usingPeg ) “ wird aufgerufen, mit den Parametern 3, „Kupfersäule“, „Goldsäule“, „Silbersäule“.

Der Parameter „n“ ist größer als als 1, somit ist die Bedingung true.

Es wird das erste Mal die move(n-1,fromPeg,usingPeg,toPeg) Methode in sich selbst aufgerufen, dieser Aufruf sieht wie folgt aus:

move(3-1,“Kupfersäule“,“Silbersäule“,“Goldsäule“).

1. Aufruf in sich selbst:

Der Parameter „n“ ist erneut größer als 1, wieder ist die Bedingung true.

Dieses Mal lautet der Aufruf der Methode move(2-1,“Kupfersäule“,“Goldsäule“,“Silbersäule“).

2. Aufruf in sich selbst:

Der Parameter „n“ ist diesmal gleich 1, und somit nicht größer als 1- die Bedingung ist also false.

Es erfolgt die Ausgabe

„Bewege Scheibe 1 von der Kupfersäule zur Goldsäule.“

Jetzt kommt es zu einem rekursiven „Aufstieg“, wenn ich es richtig verstanden habe, und die letzten Ausgaben sollten erscheinen- das hieße, es müsste folgendes ausgegeben werden:

„Bewege Scheibe 2 von der Kupfersäule zur Silbersäule.“

Nun wird die zweite, erwähnte, move(n-1,usingPeg,toPeg,fromPeg) Methode ausgeführt, was dem Aufruf von move(2-1,“Goldsäule“,“Silbersäule“,“Kupfersäule“) entspricht.

3. Aufruf in sich selbst:

Der Parameter „n“ ist erneut gleich 1, kleiner als 1 und die Bedingung ist false.

Es erfolgt die Ausgabe „Bewege Scheibe 1 von der Goldsäule zur Silbersäule“. Nun switcht er wieder zum 2. Aufruf von move(n-1,usingPeg,toPeg,fromPeg).

----

Und da fängt nun mein Problem an. In meiner Logik geh ich nun wieder einen Schritt zurück- und habe für den Aufruf die Parameterliste move(2-1,“Kupfersäule“,“Silbersäule“,“Goldsäule“). Fakt ist jedoch, dass die nächste Ausgabe für „n“ den Integer „3“ einsetzt.

Wenn ich dies nun einfach hinnehme (ohne es zu verstehen, muss ich sagen; ich geh nun halt nicht einen sondern zwei Schritte zurück) passt die Ausgabe von „Bewege Scheibe 3 von der Kupfersäule zur Goldsäule.“, es entspricht dem beginnenden Aufruf.

Zeitgleich hieße das, die nächste Ausgabe müsste eine 2 beinhalten. Tatsächlich jedoch enthält es eine 1, statt einer 2.

Egal wie verbissen ich darüber nachdenke, ich krieg einfach nicht genau raus, wie der Sprung, nach diesem 3. Aufruf, genau aussieht. Ich hab es mir auf Papier „ausgemalt“, auf dem Computer und auch einen Bekannten gefragt (der zwar keine Erfahrung mit Java hat, jedoch mit der Sprache Delphi und ein wenig C[++], wie er sagt).

Wenn ich die zwei Schritte, für die „3“ zurück gehe, muss ich daraufhin auch zwei Schritte nach vorne gehen, dass ich auf die 1 komme- und somit die „2“ erst im darauf folgenden Aufruf nutze?

*sich die Haare rauf*

[flashpixx]

Rekursion ist erst einmal sprachunabhängig. Ich hab es nur mal überflogen, aber Du scheinst alles richtig zu beschreiben. Im Grunde merkt sich der Rechner, wenn der rekursive Abstieg erfolgt, wohin er wieder springen muss, wenn die Funktion beendet wurde (deshalb mein Hinweis mal mit den Klammern). D.h. in Deinem Fall wird bei n == 1 die Ausgabe erzeugt und dann springt die Verarbeitung hinter den Punkt, wo vorher der rekursive Aufruf erfolgt: also:

move {

   do(a)

   move{  <= rekursiver Aufruf

       do(a)

       do(

   } <= nachdem das innerste move abgearbeitet wurde geht es hier weiter

   do(

}

[/code]

Bei Deinem Problem steigst Du so lange in die Rekursion hinein, bis der Parameter == 1 ist, also Abstiegt 3, 2, 1 -> Abbruch der Rekursion

so nun sind wir in 1 und springen wieder um eine Ebene hoch, also in 2 (der Wert der Übergabe verändert sich ja nicht), d.h. in 2 kommt dann der nächste Auf der Rekursion, d.h. wieder eine 1, dann springen wir wieder raus und haben 2 abgearbeitet (mit 3 analog). Malt man sich diese Aufrufe auf dann entsteht ein Baum, den nennt man auch Callgraph.

Im Grunde musst Du folgendes machen: Du musst alle Teilbäume abgearbeitet haben, bevor Du in der Rekursion wieder hoch springen darfst, wie im Beispiel bei der ersten 1, darunter kommt nichts mehr, also sind wir fertig und wir dürfen hoch in 2 springen, aber da fehlt jetzt noch das 2. move, d.h. nun müssen wir das erst vollständig abarbeiten, bevor wir die 2 wieder verlassen dürfen.

siehe ggf Baum (Graphentheorie)

[Cryver]

Vielen Dank, ich hab das Beispiel jetzt auf dem Papier beim Wert "3" und "4" komplett richtig, lediglich einige kleinere Denkfehler gehabt, die ich aber verstehen und berichtigen konnte.

Mal schauen, ob ich während meines Eigenstudiums noch einmal etwas fragen muss *schmunzel*

Ich wünsche allen zusammen einen schönen Feierabend und einen angenehmen Tag noch,

Cryv