Frage zu Rekursionen - Towers of Hanoi

[rabenau]

Hallo zusammen

Ich fange gerade erst mit dem C programmieren an und hab mal ne Frage zu Rekursionen.

#include <stdio.h>
int umleg=0;
void transportiere(int,int,int,int);
void main(void)
{
  int n;
  printf("-----------------------\n");
  printf("    Tuerme von Hanoi\n");
  printf("-----------------------\n");
  printf("Wieviele Scheiben? ");
  scanf("%d",&n);
  printf("\n");
  transportiere(n,1,2,3);
  printf("\n%d Umlegungen\n",umleg);
  return;
}

void transportiere (int anzahl,int quelle,
                    int hilfsturm,int ziel)
{
  if (anzahl>1)
    transportiere(anzahl-1,quelle,ziel,hilfsturm);
  printf("Bringe Scheibe %2d vom Turm %2d nach "
         "Turm %2d\n", anzahl,quelle,hilfsturm);
  umleg++;
  if (anzahl>1)
    transportiere(anzahl-1,ziel,hilfsturm,quelle);
}

Das Beispiel ist aus "Effektiv Programmieren in C und C++".
Kann mir jemand erklären, was genau im Unterprogramm passiert? Irgendwie verstehe ich das noch nicht ganz.

Gruß
rabenau

[Xato]

Wo ist denn genau dein Problem/dein "nicht verstehen"?

[c.rackwitz]

sollte so klarer sein.

#include <stdio.h>

int move(int ndisks, int from, int to, int spare)
{
	int moves;

	if (!ndisks)
		return 0;

	moves = move(ndisks-1, from, spare, to);

	printf("%d -> %d\n", from, to);
	moves += 1;

	moves += move(ndisks-1, spare, to, from);

	return moves;
}

int main(void)
{
	int ndisks;
	int moves;

	printf("wieviele scheiben?");
	scanf("%d", &ndisks);

	moves = move(ndisks, 1, 2, 3);

	printf("%d moves", moves);

	return 0;
}

[rabenau]

Xato schrieb:

Wo ist denn genau dein Problem/dein "nicht verstehen"?

Hmm, weiss nicht, ob ich das so gut erklären kann, aber ich versuchs.

void transportiere (int anzahl,int quelle,
                    int hilfsturm,int ziel)
{
  if (anzahl>1)
    transportiere(anzahl-1,quelle,ziel,hilfsturm);
  printf("Bringe Scheibe %2d vom Turm %2d nach "
         "Turm %2d\n", anzahl,quelle,hilfsturm);
  umleg++;
  if (anzahl>1)
    transportiere(anzahl-1,ziel,hilfsturm,quelle);
}

Der erste Schritt im UP ist ja, das der n-1 Stapel vom Quellturm auf den Zielturm verschoben wird, mit Hilfe des Hilfsturms, wenn ich das richtig verstanden habe.
Danach werden den dann die Züge ausgegeben und der Zähler um einen erhöht.

Was ich nicht verstehe, ist der Schritt danach. Warum wird der n-1 Stapel vom Zielturm über den Quellturm auf den Hilfsturm verschoben, und vor allem, wieso passiert das erst nach der Ausgabe der Züge; wenn ich die zweite if-Anweisung testweise weglasse, werden nur 3 Züge gemacht.

Irgendwie verstehe ich also noch nicht so genau, was da eigentlich wirklich passiert. Stimmt es überhaupt, das die Anweisung lautet:
transportiere(Anzahl_Platten - 1, von, nach, über)?

Ich hoffe, das wahr wenigstens etwas verständlich.

Gruß
rabenau

[c.rackwitz]

um einen n-turm von A nach B zu verschieben (mit C als spare), mache man:
die obersten n-1 scheiben von A nach C
eine scheibe von A nach B
die n-1 scheiben von C nach B

das dann rekursiv, bis n-1 == 0