Rekursion und die Türme von Hanoi

[Brei]

Hallo, hab da ein Denkproblem. Hab aus einem PHP Buch das Beispiel, ich schaff es aber nicht durchzublicken. Kanns mir jemand verständlich erklären?

function Turm($i, $s, $z, $h) {

    if ($i>0)  {

		Turm ($i-1, $s, $h, $z);

		echo("Bewege Scheibe $i vom $s zum $z<br>");

		Turm ($i-1, $h, $z, $s);

    }

}


Turm (5,'Startturm','Zielturm','Ausweichplatz');


[/PHP]

[kingofbrain]

Servus,

die Funktion macht Folgendes:

function Turm($i, $s, $z, $h) {

    if ($i>0)  {

        Turm ($i-1, $s, $h, $z);

        echo("Bewege Scheibe $i vom $s zum $z<br>");

        Turm ($i-1, $h, $z, $s);

    }

}


Turm (5,'Startturm','Zielturm','Ausweichplatz'); 

[/PHP]

Beim Start gibst Du das oberste Element an und drei Plätze. Dann ruft die Funktion solange sich selber auf und dekrementiert die Zählvariable (das Stockwerk), bis sie bei eins ist. Dann wird das erste mal etwas ausgegeben, da, die zuletzt aufgerufene Funktion zurückkehrt, ohne etwas getan zu haben (die if-Bedingung war falsch). Es wird die Scheibe 1 Start zum Ziel gebracht. Danach wird wieder die Funktion aufgerufen, kehrt aber auch zurück, ohne was zu tun, weil die Bedingung auch hier falsch ist.

Es kehrt jetzt die vorletzte Funktion zurück und gibt aus, dass sie die Scheibe vom Start zum Ausweichplatz gebracht hat. So geht das weiter.

Du musst Dir immer überlegen, wieviele Funktionen im Moment auf dem Stack liegen, wohin also eine Funktion nach Ihrer Beendigung zurückkehrt.

Am Besten hilft dabei ein grosses Blatt Papier, wo Du jeden einzelnen Schritt mitzeichnest.

Ich glaube allerdings, dass dieses Beispiel die Türme von Hanoi nicht richtig umsetzt. Ich habe allerdings mein Beispiel nicht hier.

Peter