Rekursive Algorithmen
Rekursive Prozeduren
Im vorigen Schritt hieß es so gegen Ende:
Du baust den Turm aus den n Scheiben im Zwischenlager (LAGER) statt im ZIEL auf, was ich als bekannt unterstelle, um dann die unterste (n+1)-Scheibe auf der Nadel ZIEL abzulegen. Jetzt kannst Du mühelos den zwischengelagerten Turm aus n Scheiben auf die größte Scheibe versetzen. – Damit ist das Grundprinzip klar.
Bei diesen Überlegungen haben wir uns auf die Bottom-Up-Methode gestützt: kleine Teillösungen => große Strukturen; von n zu n+1. Aber am Anfang von Schritt 4 waren wir uns einig darüber, dass wir es „mit der Top-Down-Methode versuchen“ wollten; also Riesenproblem in kleine Teillösungen zerlegen, bis diese „programmierbar“ erscheinen; also von n zu n-1.
Wir fassen diese Überlegungen in einem Algorithmus zusammen:
Arbeitsauftrag: Bewege n Scheiben von der Nadel START auf die Nadel ZIEL.
|
Bitte beachte, dass für jeden Arbeitsauftrag START, ZIEL und LAGER die Plätze wechseln.
Um diese Arbeitsaufträge realisieren zu können, verwenden wir folgende Prozedur, die diese Überlegungen widerspiegelt:
procedure bewege (n: Integer; Start, Ziel, Lager: Char); begin if n > 1 {unsere Abbruchsbedingung} then bewege (n-1, Start, Lager, Ziel); {Rekursion => Selbstaufruf} { hier kommt die Ausgabe "bewege [Start] nach [Ziel]" } if n > 1 {unsere Abbruchsbedingung} then bewege (n-1, Lager, Ziel, Start) {Rekursion => Selbstaufruf} end; {der Prozedur bewege}
Um die Prozedur ausprobieren zu können, rufe das Programm Motor.exe (aus der Datei TutExe.exe) auf. Dabei wird folgende Ausschrift angezeigt:
1 Bewege den Würfel von <A> nach <B>. 2 Bewege den Würfel von <A> nach <C>. 3 Bewege den Würfel von <B> nach <C>. 4 Bewege den Würfel von <A> nach <B>. 5 Bewege den Würfel von <C> nach <A>. 6 Bewege den Würfel von <C> nach <B>. 7 Bewege den Würfel von <A> nach <B>.
Tatsächlich liefert die einfache kurze Prozedur das gewünschte Ergebnis.
Das Beispiel zeigt, wie kurz und leistungsfähig rekursive Prozeduren sein können.
Übrigens: Den Quelltext für die Prozedur bewege findest Du in uMotor.pas.