|
Oft werden Rekursionen dazu eingesetzt, um ein komplexes Problemlösungsverfahren in viele kleine, einfach zu lösende, Teilschritte aufzuspalten, durch deren Ausführung die gestellte Aufgabe schließlich gelöst werden kann.
Das Aufspalten erfolgt in mehreren Stufen, sodaß dieser Prozeß am besten mit einem Baumdiagramm darzustellen ist. Diese Baumstruktur verästelt sich, vom gegebenen Problem ausgehend, schrittweise in immer mehr und kleinere Probleme, bis diese leicht zu lösen sind. Bei den Baumdiagrammen unterscheidet man zwei Typen: den einfachen, bzw. linearen, und den mehrfach verzweigten, bzw. unlinearen Typ, je nachdem, wie viele Verzweigungen von den Knotenpunkten des Baumes ausgehen. Bei linearen Bäumen hält sich die Größe der Struktur in Grenzen - mit jedem Lösungsschritt gibt es einen Ast mehr, und auch der Speicheraufwand steigt linear zur Anzahl der Lösungsschritte. Bei doppelt verzweigten Strukturen wächst der Speicheraufwand quadratisch mit der Anzahl der Lösungsschritte, bei dreifach verzweigten kubisch, und so weiter.
Folgende Programme dienen nicht nur als theoretisches Beispiel, sondern sind auch in der Praxis effizient einzusetzen.
3.2.1 Die ggT Berechnung nach Euklid
Der griechische Mathematiker Euklid fand ein Verfahren, das es ermöglicht, den größten gemeinsamen Teiler (ggT) zweier Zahlen ohne Primfaktorenzerlegung zu berechnen. Beim Euklidischen Algorithmus (oder Kettendivision) wird zuerst der Rest R der Division der Zahl Z1 und der Zahl Z2 gebildet. Dann wird der Divisor Z2 durch den Rest R dividiert und der neue Rest gebildet. Mit diesem Verfahren fährt man so lange fort, bis man als Rest Null erhält, der letzte Rest, der größer als Null ist, teilt dann alle vorherigen Divisoren und Dividenden und ist somit ggT der Zahlen Z1 und Z2.
Dieser Algorithmus läßt sich als rekursive Funktion programmieren. Das komplexe Problem, den ggT zweier Zahlen zu suchen, beschränkt sich auf die einfache Kontrolle, ob der Rest der Division zweier Zahlen Null ist. Da sich das rekursive Unterprogramm nur einmal selbst aufruft, steigt der Speicheraufwand linear mit der Anzahl der Lösungsschritte.
Die Funktion ggT sieht folgendermaßen aus:
function ggT(z1, z2 :integer);
begin
if z2=0 then ggt:=z1else ggt:=ggt(z2, z1 mod z2);
end;
(Den Rest des Programmes ist im Anhang zu finden)
Ist der Rest der letzten Division, der in z2 übergeben wurde, Null, dann ist der vorige Rest in z1 der ggT. Andernfalls ruft sich die Funktion mit dem Rest der letzten Division z2 und dem Rest der neuen Division (z1 mod z2) selbst auf. Im Speicher bildet sich beim Aufruf von ggt(64,52) folgende Baumstruktur:
ggt(64,52) -- ggt(52,12) -- ggt (12,4)
Dann bricht die Rekursion ab, da der Rest der Division Zwölf durch Vier Null ist.
3.2.2 Quicksort
Quicksort ist , wie der Name bereits andeutet, ein sehr schnelles, natürlich rekursives Sortierverfahren. Der Quicksort-Algorithmus ist das Paradebeispiel für das Lösen komplexer Probleme durch Zerteilung:
In einem eindimensionalen Feld (Vektor) werden Daten gespeichert. Dann wird das rekursive Quicksort-Unterprogramm aufgerufen, wobei ihm als Parameter der Start- sowie der Endindex des zu sortierenden Feldbereiches übergeben werden. Der Algorithmus nimmt einen Wert aus diesem Feldbereich heraus (meistens den mittleren) und teilt den zu sortierenden Bereich somit in eine linke und in eine rechte Hälfte. Dann werden alle Werte im linken Teil, die größer sind als der herausgenommene Wert, mit einem aus dem rechten Teil, der kleiner ist als der Trennwert, vertauscht. Danach steht der Trennwert bereits an der richtigen Stelle.
Hierauf ruft sich das Unterprogramm zweimal selbst auf, um den linken und den rechten Teil nach dem obigen Schema zu sortieren.
Nun folgt der Quellcode des Quicksort-Algorithmus (a ist ein global definiertes array of integer). Die Erläuterung der einzelnen Programmstellen erfolgt erst nach dem Programmcode unter der jeweils zugeordneten Zahl:
procedure quicksort(l, r: integer);
var i, j, x, hilf: integer;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2]; {1}
repeat
while a[i]< x do inc(i); {2}
while a[j]> x do dec(j); {3}
if ij; {7}
if li then quicksort(i,r);
end;
Das vollständige Beispielprogramm sorter.pas ist auf der Begleitdiskette zu finden, das die Effiziens des Quicksort-Algorithmus und des Minimumsort-Verfahren im Vergleich zeigt. Der komplette Quellcode dieses Programmes ist im Anhang (A2, "sorter") abgedruckt.
Zuerst wird das mittlere Element als Trennelement in der Variablen x zwischengespeichert {1}. Die beiden Teilbereiche werden nacheinander von außen nach innen zum Trennelement hin durchlaufen. Im linken Teil wird ein Element gesucht {2}, das größer als das Trennelement ist, im rechten eines, das kleiner ist {3}. Dann werden diese Elemente, wenn sie wirklich in der falschen Hälfte liegen {4}, ausgetauscht {5}. Schließlich geht der Algorithmus sowohl in der linken als auch in der rechten Hälfte um eine Position weiter {6}, um nicht noch einmal die selben Elemente miteinander zu vergleichen. Es werden solange Elemente ausgetauscht, bis beide Seiten zur Gänze durchlaufen wurden {7}. Dann werden beide Teilmengen, wenn sie noch aus mehr als einem Element bestehen, durch einen Selbstaufruf der Prozedur quicksort sortiert {8}. Die Größe des Sortierbereiches wird somit mit jedem neuerlichen Prozeduraufruf halbiert. Da ein zweifacher Selbstaufruf erfolgt ist, besitzt der Quicksort-Algorithmus eine doppelt verzweigte Baumstruktur.
Der iterative Sortieralgorithmus Bubblesort benötigt beim Sortieren eines Feldes mit 1000 Werten durchschnittlich etwa 50 mal so viele Vergleiche wie der Quicksort-Algorithmus. Unter bestimmten Bedingungen kann dieser jedoch entarten, sodaß beinahe so viele Vergleiche notwendig sind wie beim Bubblesort. Dies kann passieren, wenn der Wert des Trennelements sehr hoch oder sehr niedrig ist. Denn dann wird der zu sortierende Bereich nicht halbiert, sondern bleibt beinahe unverändert. Je häufiger ein extremer Wert als Trennwert genommen wird, desto langsamer wird der Quicksort-Algorithmus.
3.2.3 Die Türme von Hanoi
Eines der bekanntesten Beispiele für eine praktische Anwendung der Rekursion ist das altchinesische Brettspiel \'Die Türme von Hanoi\'. Es besteht aus einer Platte, auf der drei Stäbe senkrecht aufgestellt sind. Auf einem von ihnen befindet sich eine nach Belieben wählbare Anzahl von Scheiben mit verschiedenen, nach oben hin stetig abnehmenden Radien. Ziel des Spieles ist es, alle Scheiben in gleicher Anordnung auf den dritten Stab umzuschichten, wobei der zweite als Hilfe verwendet werden kann. Es darf immer nur eine Scheibe bewegt werden, und diese darf nur auf einer Scheibe mit größerem Radius zu liegen kommen.
Ist nur eine Scheibe vorhanden, kann sie direkt vom ersten auf den dritten Stab gelegt werden. Bei zwei Scheiben muß die erste Scheibe auf dem zweiten Stab zwischengelagert werden, damit die zweite Scheibe vom ersten auf den dritten Stab gebracht werden kann. Liegen drei Scheiben auf dem ersten Stab, müssen folglich zwei Scheiben zuerst auf den zweiten Stab gebracht werden, um die dritte Scheibe ans Ziel bringen zu können. Dann muß die kleinste Scheibe am nun leeren ersten Stab zwischengelagert werden, um die mittlere Scheibe auf den dritten Stab legen zu können. Schließlich kann dann auch die kleinste Scheibe auf den Turm geschichtet werden.
Der Arbeitsaufwand wächst mit jeder Scheibe enorm an. Doch auch hier kann man das komplexe Problem der Umlagerung der Scheiben mit Hilfe der Rekursion in kleine Teilprobleme aufteilen: Alle Scheiben mit Ausnahme der jeweils größten werden auf einem freien Stab, im Folgenden Puffer genannt, zwischengelagert, so daß die verbleibende letzte Scheibe problemlos ans Ziel gebracht werden kann. Dieser Vorgang wird so lange wiederholt, bis alle Scheiben umgelagert worden sind. Obwohl dieser Vorgang kompliziert klingt, ist er dennoch einfach zu programmieren:
procedure hanoi(anzahl, quelle, puffer, ziel :integer);
begin
if anzahl=1 then writeln(\'Scheibe von \',quelle,\' nach \',ziel,\'.\') else begin {1}
hanoi(anzahl-1, quelle, ziel, puffer); {2}
writeln(\'Scheibe von \',quelle,\' nach \',ziel,\'.\'); {3}
hanoi(anzahl-1,puffer, quelle, ziel); {4}
end;
end;
Der Aufruf der Prozedur hanoi (4,1,2,3) würde also alle Schritte, die für das Umschichten vom ersten auf den dritten Stab unter der Zuhilfenahme des zweiten notwendig sind, am Bildschirm ausgeben. Beim vollständigen Programm, das im Anhang (A3, "Tuerme_von_Hanoi") abgedruckt ist, kann der Benutzer die Zahl der Scheiben frei wählen. Die Anzahl der notwendigen Züge steigt jedoch exponential mit der Scheibenzahl. Für n Scheiben sind immer 2n - 1 Züge notwendig. Diesen Zusammenhang erhält man, da sich das rekursive Unterprogramm zweimal selbst aufruft.
Die Idee der Prozedur ist, daß eine Scheibe direkt ans Ziel gebracht wird, wenn dies möglich ist {1}. Anderenfalls werden zuerst alle darüberliegenden Scheiben auf den Pufferstab gebracht {2}, dann wird die erste Scheibe auf den Zielstab gelegt {3}, und schließlich werden alle andern Scheiben ebenfalls ans Ziel gebracht {4}. Der genaue Rekursionsablauf, der dem Aufruf hanoi (3,1,2,3) folgt, ist folgender:
hanoi(3,1,2,3); 321
hanoi(2,1,3,2); 321
hanoi(1,1,2,3); 321
writeln(\'Scheibe von 1 nach 3.\'); 32 1
writeln(\'Scheibe von 1 nach 2.\'); 3 2 1
hanoi(1,3,1,2); 3 2 1
writeln(\'Scheibe von 3 nach 2.\'); 3 21
writeln(\'Scheibe von 1 nach 3.\'); 21 3
hanoi(2,2,1,3); 21 3
hanoi(1,2,3,1); 21 3
writeln(\'Scheibe von 2 nach 1.\'); 1 2 3
writeln(\'Scheibe von 2 nach 3.\'); 1 32
hanoi(1,1,2,3); 1 32
writeln(\'Scheibe von 1 nach 3.\'); 321
Je weiter die Zeilen eingerückt sind, desto tiefer ist die Rekursionsebene. Die Zahlenreihen auf der linken Seite zeigen die Stäbe eins bis drei. Die Zahlen selbst repräsentieren die Scheiben, wobei Eins für die mit dem kleinsten Radius steht, und Drei für die mit dem größten. Das rechte Ende der Zahlenreihen ist die Spitze des Stabes.
4 |
