Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel. In der Informatik gilt es als Standardbeispiel für rekursive Programmierung. Das Spiel wird von einer Person gespielt. Es besteht aus drei gleich großen Stäben, auf die mehrere gelochte Scheiben gesteckt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf dem linken Stab, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel vom linken Stab auf den rechten Stab zu versetzen. Hierbei gelten zwei Regeln:
Es darf immer nur eine Scheibe gleichzeitig bewegt werden.
Die bewegte Scheibe darf nicht auf eine kleinere Scheibe gesteckt werden.
Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet. Da sich ein Computerprogramm zur Lösung des Spiels mit wenigen Zeilen schreiben lässt, ist Türme von Hanoi ein klassisches Beispiel für diese Art der Problemlösung. Der Algorithmus besteht im Wesentlichen aus einer Funktion bewege, die vier Parameter besitzt. Mit i ist die Anzahl der zu verschiebenden Scheiben bezeichnet, mit a der Stab, von dem verschoben werden soll, mit b der Stab, der als Zwischenziel dient, und mit c der Stab, auf den die Scheiben verschoben werden sollen. Zur Lösung des eigentlichen Problems wird bewege mit i = n, a = A, b = B und c = C aufgerufen. – Mehr erfahren …