Home » Tutorials » Programmierkonzepte » Rekursive Algorithmen

Rekursive Algorithmen

Rekursion

Im tiefen Keller sitz‘ ich hier und – kann mich vor Daten nicht mehr retten. Sieh Dir deshalb noch einmal Schritt Speicherorganisation an.

1. Das allgemeine Prinzip der rekursiven Problemlösung

Zur Lösung des Problems „Türme von Hanoi“ haben wir einen rekursiven Algorithmus formuliert, der stets einfachere Varianten von sich selbst enthält. Die Bearbeitung des Falles n = 5 wurde mit der einfacheren Variante n – 1 = 4 beschrieben usw. Das ist das Prinzip des rekursiven Algorithmus.

Ein Algorithmus ist ein rekursiver Algorithmus, wenn er mit Hilfe einfacher Varianten von sich selbst beschrieben wird.

Die Prozedur bewege aus Schritt Rekursive Prozeduren ist die direkte programmtechnische Umsetzung des zunächst bildhaft formulierten rekursiven Algorithmus für das Stapeln von Scheiben. Da der Algorithmus rekursiv ist, ist auch die direkte Übersetzung in die Prozedur bewege rekursiv.

Man erkennt die Rekursion daran, dass sich die Prozedur bewege selbst aufruft.

Wir nennen Prozeduren, die sich selbst aufrufen, rekursive Prozeduren bzw. rekursive Funktionen.

In unserem Beispiel der „Türme von Hanoi“ ist die einfachste Variante des Algorithmus für das Stapeln von n Scheiben der Fall n = 1. Bei n = 1 dürfen keine weiteren rekursiven Aufrufe von bewege erfolgen.
In unserer Prozedur erfolgt deshalb nur dann ein weiterer Aufruf innerhalb der Prozedur, wenn n größer als 1 ist. Hier ist eine Abbruchbedingung für die rekursive Prozedur formuliert, ähnlich der Abbruchbedingungen in einer Schleife. Natürlich muss sichergestellt werden, dass die Abbruchbedingung auch erreicht wird. Andernfalls käme es zu einer unendlichen Rekursion!!

Jeder rekursive Algorithmus und jede rekursive Prozedur muss eine (wirklich zu erreichende) Abbruchbedingung enthalten.

Um die Wirkungsweise der Rekursion besser verstehen zu können, einigen wir uns auf zwei Begriffe:

  1. Die Bestimmung der nächsteinfacheren Variante eines Problems nennen wir Rekursionsschritt.
  2. Die nach einem Rekursionsschritt erreichte Variante nennen wir Rekursionsstufe.

Probleme, die ihrer Natur nach zur Strategie „Teile und Herrsche“ passen, lassen sich besonders gut rekursiv lösen.
Damit ein Problem ein Kandidat für eine rekursive Lösung nach dem Prinzip „Teile und Herrsche“ ist, muss es folgende Eigenschaften besitzen:

  1. Das Originalproblem muss sich in einfachere Varianten von sich selbst zerlegen lassen.
  2. Die Zerlegung in Teilprobleme muss zuletzt auf so einfache Varianten des Originalproblems führen, dass sie ohne weitere Zerlegung gelöst werden können.
  3. Wenn alle Teilprobleme gelöst sind, müssen die Lösungen so zusammengesetzt werden können, dass sich eine Lösung des Originalproblems ergibt.

2. Techniken der rekursiven Programmierung

Der in Schritt Speicherorganisation genannte Kellerspeicher (Stack) ist ein Speicherbereich, der auf besondere Art und Weise organisiert ist: gleich einem Bücherstapel kann ein Speicherwert NUR OBEN AUFGELEGT UND AUCH NUR OBEN WIEDER ABGENOMMEN werden.
Um besser verstehen zu können, wie Rekursion programmtechnisch funktioniert, sehen wir uns die nachfolgende Skizze an.
Die Skizze zeigt die Prozedur LiesZeichen mit einer lokalen Variablen Z. Diese Prozedur liest bei ihrem Aufruf EIN Zeichen ein. Das Abbruchskriterium ist das Zeichen |#|.
Auf dieser Skizze sind von der ersten Rekursionsstufe aus drei Rekursionsschritte dargestellt; das bedeutet, die Prozedur hat sich nach ihrem ersten Aufruf noch dreimal selbst aufgerufen. Die Abbruchsbedingung wurde auf Rekursionsstufe (4) eingegeben. Die Rekursionsstufen (1) bis (4) sind voneinander abgesetzt dargestellt.
Auf der letzten Zeile wird die Arbeitsweise der Prozedur durch die Bildschirmausschrift belegt.

========================================================================
 +-----------------------
(1) LiesZeichen                                 ||#| = Abbruchbedingung
Eingabe: Z <= |R| +-----------------------
 +-----------------------------------------------------------
Z <> |#| =====> (2) LiesZeichen
 |   Eingabe: Z <= |O|
 |               +-------------------------------------------
 |   Z <> |#| =====> (3) LiesZeichen
 |               |   Eingabe: Z <= |M|
 |               |               +---------------------------
 |               |   Z <> |#| =====> (4) LiesZeichen
 |               |               |   Eingabe: Z <= |#|
 |               |               |   Z = |#| ABBRUCH !
 |               |               | (4) Ausgabe |#|
 |               |               +---------------------------
 |               | (3) Ausgabe |M|
 |               +-------------------------------------------
 | (2) Ausgabe |O|
 +-----------------------------------------------------------
(1) Ausgabe |R|

========================================================================

Bildschirmausgabe: R O M # # M O R

========================================================================

Um die Prozedur LiesZeichen auch ausprobieren zu können, liegt die Turbo-Pascal-Datei rekursio.pas den Beispieldateien bei. Sie zeigt nur die unbedingt zum Verständnis notwendigen Daten. Die Datei Rekursio.exe (in TutExe.exe), die nur im DOS-Bildschirm läuft, kann durch Anklicken aufgerufen werden. Hier kannst Du selber probieren.
Und nun steht die große Frage im Raum:

Wie werden die einzelnen Zeichen gespeichert, wenn wie hier nur EINE Variable in der Prozedur vorhanden ist?
Die Frage lässt sich insofern leicht beantworten, wenn Du Dir klar machst, dass die Variable Z eine lokale Variable innerhalb der Prozedur LiesZeichen ist.

Für lokale Variablen werden erst bei Prozeduraufruf Speicherzellen auf dem Stack zur Verfügung gestellt und erst dann wieder freigegeben, wenn die Abarbeitung der Prozedur beendet ist.

Das hat zur Folge, dass bei jedem Prozeduraufruf für die Variable Z auf dem Stack andere Speicherzellen verwendet werden – die allerdings auf jeder Rekursionsstufe den gleichen Namen haben.
Wenn Du mehr über lokale Variablen und ihren Geltungsbereich wissen möchtest, kann ich Dir nur „Pascal-Grundlagen * Variablen und Konstanten“ hier auf DSDT empfehlen.
Auch in der Prozedur bewege aus Schritt Rekursive Prozeduren funktioniert die rekursive Programmierung nur, weil die Werteparameter der Prozedur bewege wie lokale Variablen behandelt werden.
Und hier die Prozedur zur Erinnerung in Kurzform:

procedure bewege (n: Integer; Anfang, Ende, Mitte: Char);
begin
  if n > 1 then bewege (n-1, Anfang, Mitte, Ende);
  if n > 1 then bewege (n-1, Mitte, Ende, Anfang);
end {bewege};

Du siehst, in der Kürze liegt die Würze. Und die Hauptarbeit leisten die Werteparameter. Beachte dabei, dass die Reihenfolge der Parameter stets geändert ist. Darin liegt das Geheimnis dieser Prozedur!!
Das muss ich hier doch noch einfügen:
Ich bin immer wieder erstaunt darüber, wie kurz rekursive Prozeduren oder Funktionen sein können. Eigentlich wird die Kopfleiste der Prozedur mit Parametern dreimal untereinander geschrieben – freilich mit veränderter Parameter-Reihenfolge – und dann hat es sich schon. Und wo ist der eigentliche Quellcode? Du verstehst sicher, dass mich das in Erstaunen versetzt, zumal das Ergebnis so ungeheuer ist. Da würde ich auf Befragen einen Quelltext von mehreren hundert Zeilen erwarten.
Rekursive Programmierung ist doch etwas Tolles. Auch wenn sie so „harte Nüsse“ bereitstellt. Also: (siehe Einführung) Geduld lohnt sich!!
Aber jetzt noch einmal:

Werteparameter von Prozeduren und Funktionen werden bei der rekursiven Programmierung wie lokale Variablen verwaltet.

Übrigens: Auch über Werteparameter und Variablenparameter kannst Du Dich wenn nötig bei DSDT informieren: Pascal-Grundlagen * Prozeduren und Funktionen.