Rekursive Algorithmen
Modularisierung
Um eine größere Programmieraufgabe zu lösen, müssen wir uns – vor allen Überlegungen über Algorithmen, vielleicht gar noch rekursive – zuerst einmal über die Möglichkeiten klar werden, die uns zur Verfügung stehen, um unser „Riesen“problem erfolgreich lösen zu können.
In den Pascal-Grundlagen hier bei Delphi-Source las ich neulich: Die objektorientierte Programmierung „soll die unstrukturierte Programmierung (am Anfang ein begin, dann Befehl auf Befehl und am Ende ein end, dazwischen möglichst viele Sprünge mit goto) ablösen.“ – In einem Lehrgang über Turbo Pascal kurz nach der Wende erlebte ich einen Mitteilnehmer, der ein doch etwas längeres Pascal-Programm „in einem Ritt“ aufschrieb, also wirklich hintereinander, nur mit den Leer- oder Trennungszeichen, wenn sie Pascal unbedingt haben wollte. Und, o Wunder!, das Programm machte sogar, was es sollte.
(Würdest Du in so einem Programm Fehler suchen wollen?).
Um weder den einen noch den anderen Programmstil anwenden zu müssen, haben wir uns an den modularen Programmierstil gewöhnt.
Das Modularisierungs-Prinzip „Teile und Herrsche“
Dazu gehört zunächst, eine Aufgabe (unser „Riesen“problem) in einfachere Teilaufgaben zu zerlegen. Die Lösung der Teilaufgaben wird in Form von Prozeduren und Funktionen programmiert. Die Definition geeigneter Datenstrukturen kann die Formulierung einer Lösung wesentlich erleichtern.
In dem beiliegenden Programm Hanoi habe ich zum Beispiel in der Unit uHanoiDef, der Unit, die die Definitionen enthält, einen Datentyp
TZiele = (zuPlatzB, zuPlatzC);
definiert. Der dient mir dazu, mit diesen zwei Werten in einer Prozedur jeweils ein bestimmtes Ziel festzulegen. Ich hätte da auch eine ganz allgemeine Formulierung ohne extra Datentyp verwenden können, aber so ist der Quelltext wesentlich einfacher zu lesen, für andere Programmierer und nach Wochen und Monaten auch für mich.
Wenn ich mich an so ein Modularisierungsprinzip halten will, kann ich dieses Zerlegen in Teilaufgaben auf zweierlei Art lösen:
1. Die Top-Down-Methode
Eine Programmentwicklung nach der Top-Down-Methode geht von der Leitfrage aus: Aus welchen Teilproblemen besteht die gestellte Aufgabe? Diese Teilprobleme werden immer weiter aufgegliedert, bis sie „programmierbar“ erscheinen.
Wir werden weiter unten in einem Bild noch sehen, dass das Modularisierungsprinzip „Teile und Herrsche“ nach dieser Methode arbeitet. Wir können auf dem Bild aber auch erkennen, dass es rekursiv angelegt ist, also durch einfachere Varianten von sich selbst beschrieben wird.
2. Die Bottom-Up-Methode
Beim Vorgehen nach der Bottom-Up-Methode werden zunächst kleine Teillösungen entwickelt, die schrittweise zu größeren Strukturen aufgebaut werden.
Auch hier werden wir in einem späteren Schritt den Zusammenhang dieser Methode mit einem Verfahren, das iterativ arbeitet, erkennen können.
Das Prinzip von „Teile und Herrsche“ (divide et impera):
procedure LöseDasProblem;
begin
if Problem_ist_einfach then
Löse_das_Problem_direkt
else
begin
Zerlege_das_Problem_in_die_Teilprobleme_
Problem1, Problem2, Problem3 usw.,
Löse (Problem1); Löse (Problem2); usw.
Setze die Teillösungen P1, P2, P3 usw. zusammen
end;
end;