Home » Tutorials » Programmierkonzepte » Rekursive Algorithmen

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.

  1. Wenn n > 1, erteile folgenden Arbeitsauftrag: // Abbruchkriterium
    Bewege n-1 Scheiben von der Nadel START auf die Nadel LAGER.
  2. Bringe eine Scheibe von der Nadel START auf die Nadel ZIEL.
  3. Wenn n > 1, erteile Arbeitsauftrag:
    Bewege n-1 Scheiben von der Nadel LAGER 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.