Die Türme von Hanoi

Als weiteres Beispiel einer rekursiven Prozedur lösen wir das Problem der Türme von Hanoi, das Wikipedia so beschreibt:

Das Spiel besteht aus drei gleich großen Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von A nach C zu versetzen.

Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes unter der Voraussetzung, dass sich dort nicht schon eine kleinere Scheibe befindet, auf einen der beiden anderen Stäbe gelegt werden. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.

Die folgende Prozedur ist parametrisiert über die initiale Anzahl n der zu versetzenden Scheiben und gibt Anweisungen der Form Lege eine Scheibe von X nach Y aus, wobei für X und Y jeweils einer der Stäbe A, B oder C eingesetzt wird.

def hanoi(n):
  hanoi_rec(n, 'A', 'B', 'C')

Um n Scheiben von Stab A über Stab B zu Stab C zu versetzen, können wir, falls n größer als 1 ist, zunächst n-1 Scheiben von A über C nach B versetzen, dann die größte Scheibe von A nach C legen und schließlich die n-1 Scheiben von Stab B über A nach C versetzen. Die Prozedur hanoi_rec() implementiert diese Idee für beliebige Start, Hilfs- und Ziel-Stäbe¹

def hanoi_rec(n, source, over, sink):
  if n == 1:
    print('Lege eine Scheibe von ' + source + ' nach ' + sink + '.')
  else:
    hanoi_rec(n-1, source, sink, over)
    print('Lege eine Scheibe von ' + source + ' nach ' + sink + '.')
    hanoi_rec(n-1, over, source, sink)

Im Folgenden veranschaulichen wir die Ausführung des Aufrufs hanoi(3):

hanoi(3)
hanoi_rec(3, 'A', 'B', 'C')
Die Abbruchbedingung ist nicht erfüllt.
  hanoi_rec(2, 'A', 'C', 'B')
  Die Abbruchbedingung ist nicht erfüllt.
    hanoi_rec(1, 'A', 'B', 'C')
    Die Abbruchbedingung ist erfüllt.
    print('Lege eine Scheibe von A nach C.')
  print('Lege eine Scheibe von A nach B.')
    hanoi_rec(1, 'C', 'A', 'B')
    Die Abbruchbedingung ist erfüllt.
    print('Lege eine Scheibe von C nach B.')
print('Lege eine Scheibe von A nach C.')
  hanoi_rec(2, 'B', 'A', 'C')
  Die Abbruchbedingung ist nicht erfüllt.
    hanoi_rec(1, 'B', 'C', 'A')
    Die Abbruchbedingung ist erfüllt.
    print('Lege eine Scheibe von B nach A.')
  print('Lege eine Scheibe von B nach C.')
    hanoi_rec(1, 'A', 'B', 'C')
    Die Abbruchbedingung ist erfüllt.
    print('Lege eine Scheibe von A nach C.')

Die gesamte Ausgabe des Aufrufs ist also folgende:

>>> hanoi(3)
Lege eine Scheibe von A nach C.
Lege eine Scheibe von A nach B.
Lege eine Scheibe von C nach B.
Lege eine Scheibe von A nach C.
Lege eine Scheibe von B nach A.
Lege eine Scheibe von B nach C.
Lege eine Scheibe von A nach C.

Im einzelnen nachzuvollziehen, welche Ausgabe in rekursiven Prozeduren wann erzeugt wird, ist oft trickreich, besonders dann, wenn Ausgaben nach rekursiven Aufrufen erfolgen. Häufig ist es jedoch gar nicht notwendig, die Ausführung rekursiver Programme im Detail nachzuvollziehen. Es genügt oft, das Verhalten rekursiver Aufrufe unabhängig von deren Implementierung zu betrachten.