Fachbereichsarbeit aus Informatik - Rekursive VerfahrenFachbereichsarbeit aus Informatik Rekursive Verfahren
von Stefan Krywult geschrieben bei Hr. Prof. Herbert Paukert BG/BRG Franklinstraße 21 Abgabetermin: 12.2.1998
Inhaltsverzeichnis INHALTSVERZEICHNIS i VORWORT ii 1 DIE REKURSION ALS MATHEMATISCHES VERFAHREN 1 2 DIE REALISIERUNG VON REKURSIONEN IM COMPUTER 2 2.1 Das modulare Konzept von Pascal 2 2.2 Rekursionen in Pascal 3 3 REKURSIVE ANWENDUNGSPROGRAMME 6 3.1 Berechnung von Gliedern rekursiver Folgen 6 3.1.1 Die Fakultätsfunktion 7 3.1.2 Die Ackermann-Funktion 8 3.2 Lösungsfindung durch Zerteilen eines Problems 10 3.2.1 Die ggT Berechnung nach Euklid 10 3.2.2 Quicksort 11 3.2.3 Die Türme von Hanoi 13 3.3 Backtracking 15 3.2.1 Finden eines Weges aus einem Labyrinth 15 3.3.2 Suche nach möglichst kurzen Strecken zwischen mehreren Punkten 19 3.2.3 Das Acht-Damen-Problem 23 3.3.4 Rekursives Durchsuchen des Verzeichnisbaumes nach Dateien 26 3.4 Grafische Anwendung der Rekursion 30 3.4.1 Der fraktale Baum 30 3.4.2 Die Kochkurve 33 3.4.3 Die Sierpinsky-Dreiecke 36 ANHANG A1 A.1 Die Quellcodes aller erwähnten Programme A1 A.2 Bibliographie und Quellennachweis A9 OFFIZIELLE ERKLÄRUNG BESPRECHUNGSPROTOKOLL
Als leidenschaftlicher Hobbyprogrammierer und begeisterter Informatik-Wahlpflichtfach-Besucher wollte ich bei meiner Matura einen Schwerpunkt auf dieses interessante Fachgebiet setzen und beschloß daher, diese Fachbereichsarbeit zu schreiben. Ich habe das Thema „Rekursive Verfahren“ gewählt, weil mich die gewaltigen Möglichkeiten der rekursiven Programmierung beeindrucken: Scheinbar schwierige, beinahe unlösbar scheinende Aufgaben können mit ihrer Hilfe recht einfach bewältigt werden. Es übte einen zusätzlichen Reiz auf mich aus, daß Rekursionen dadurch, daß ihr Ablauf als ziemlich schwer zu durchschauen gilt, den Ruf des Geheimnisvollen haben. Besonders bedanken möchte ich mich bei Herrn Professor Paukert, der mir nicht nur in vielen Sitzungen die Grundlagen meiner Fachbereichsarbeit zu erarbeiten half, sondern mir auch persönliche Aufzeichnungen als Literatur für meine Arbeit zur Verfügung stellte und mich auch zwischen den Sitzungen geduldig betreute. Er vertiefte außerdem mein Interesse in das Fachgebiet der Informatik und motivierte mich beim Schreiben dieser Arbeit. Weiters möchte ich meiner Familie und vor allem meinen Eltern danken, die sich bemühten, jeden anderen Streß von mir fernzuhalten und besonders viel Verständnis für mich hatten, während ich an meiner Arbeit schrieb. Abschließend möchte ich bemerken, daß es sicherlich wesentlich einfachere bzw. weniger aufwendige Varianten der Matura gegeben hätte. Trotzdem bin ich sehr froh, diese Form gewählt zu haben, da ich auf diese Weise auf vielen verschiedenen Gebieten wichtige, interessante und schöne Erfahrungen machen konnte. Wien, 12.02.1998 1 Die Rekursion als mathematisches Verfahren In der Mathematik gibt es zwei grundlegend verschiedene Methoden, das Bildungsgesetz einer bestimmten Folge darzustellen. Bei der expliziten Beschreibung ist es möglich, ein Folgenglied direkt über die Nummer desselben auszurechnen, so zum Beispiel an=2n+1 => a4: n = 4 => a4 = 2 * 4 + 1 => a4 = 9 => a198: n = 198 => a198 = 2 * 198 + 1 => a198 = 397 Bei der rekursiven Darstellung wird das Glied nicht absolut definiert, sondern es wird nur der Zusammenhang mit dem vorigen Glied angegeben, so zum Beispiel z an = a(n-1) + 2 Um also das dritte Glied dieser Folge zu erhalten, muß zuerst das zweite ausgerechnet werden. Das zweite basiert jedoch auf dem ersten. Die Glieder müssen daher schrittweise berechnet werden. Damit der Vorgang beim ersten Glied endet, muß dieses einen festen Wert besitzen, der ebenfalls bei der Definition angegeben werden muß. Das obige Bildungsgesetz lautet daher richtig: an = a(n-1) + 2, a1 = 3 Dadurch wird dieselbe Folge wie oben definiert. Die Länge des Rechenwegs zu einem bestimmten Glied ist proportional zur Höhe der Gliednummer, während sie beim expliziten Bildungsgesetz immer gleich ist. Hier sind zum Beispiel die Rechenschritte für das dritte Glied: explizit: a3=2*3+1 a3=7 rekursiv: a3=a2+2 a2=a1+2 a1=3 a2=3+2 a3=3+2+2 a3=7 Trotz ihrer Länge ist die rekursive Darstellung oft nützlicher, da sie meistens einfacher ist und mit ihr manche Rechenarten gezielt umgangen werden können: an = x*n => an = a(n-1)+x an = x^n => an = a(n-1)*x an = n! => an = a(n-1)*n Abschließend ist zu bemerken, daß die Bildungsgesetze der meisten Folgen auf beide Arten darstellbar sind. Bei manchen ist dies jedoch nicht möglich. 2 Die Realisierung von Rekursionen im Computer Rekursive Verfahren sind nicht nur in der Mathematik, sondern auch in der Informatik von großer Bedeutung. Sie werden nicht nur zum Errechnen rekursiver Folgen, die zum Beispiel bei der Darstellung von Wachstumsprozessen oder Fraktalen Anwendung finden, sondern auch zum schrittweisen und effektiven Lösen komplizierter und langwieriger Aufgaben (zum Beispiel bei Sortieralgorithmen oder Backtrackingprogrammen) verwendet. Während früher solche Verfahren auch wirklich rekursiv programmiert wurden, werden sie heute meistens in einer leichter verständlichen iterativen, d.h. nicht rekursiven, Form verwirklicht, was es Programmierern wesentlich erleichtert, sich in Programmen ihrer Kollegen zurechtzufinden. In diesem Kapitel wird anhand der Programmiersprache Pascal die Programmierung und die Funktionsweise rekursiver Programme erklärt. Dazu muß vorher das modulare Konzept der Programmiersprache Pascal, an der die Verwendung rekursiver Verfahren demonstriert werden soll, näher betrachtet werden. 2.1 Das modulare Konzept von Pascal Die Programmiersprache Pascal ermöglicht die Verwendung von sogenannten Unterprogrammen in Form von Prozeduren und Funktionen. Der einzige Unterschied zwischen den beiden ist, daß Funktionen nach dem Aufruf einen Wert besitzen und Prozeduren nicht. Unterprogramme sind eigenständige Programmabschnitte, die aus dem Hauptprogramm, aber auch aus anderen Unterprogrammen, aufgerufen werden können. Ihre Verwendung ist von großem Vorteil, da sie das Programm übersichtlicher gestalten. So können lange Befehlsketten, die immer wieder vorkommen, durch einen einzigen Befehl, nämlich einen Unterprogrammaufruf, ersetzt werden. Dieser Aufruf wird Call genannt. Bei einem Call werden auf dem Stack folgende Informationen gespeichert:
Die Verwaltung des Stacks erfolgt nach dem LIFO-Prinzip (Last In - First Out) wobei der zuletzt abgelegte Wert als erstes wieder gelesen wird. Den Vorgang, Daten auf den Stack zu legen, nennt man Push. Beim Verlassen eines Unterprogrammes ermöglicht die zuvor auf den Stack geschriebene Rücksprungadresse die Rückkehr zum aufrufenden Programmteil (RET). Der Speicherplatz der lokalen Variablen wird wieder freigegeben, und auf dem Stack liegende Werte werden in umgekehrter Reihenfolge wieder abgehoben. Dieser Prozeß wird POP genannt. Vom Stack entfernte Daten sind unwiderruflich gelöscht. In Pascal ist es möglich, auch aus einem Unterprogramm heraus ein anderes Unterprogramm aufzurufen. Es ist sogar zulässig, daß ein Unterprogramm während seines Ablaufes sich selbst noch einmal aufruft. Diesen Selbstaufruf nennt man Rekursion. 2.2 Rekursionen in Pascal Bei der rekursiven Definition von Folgen, die im vorigen Kapitel beschrieben wurde, ist es notwendig, das erste Glied a1 absolut zu bestimmen, indem man ihm einen Zahlenwert zuweist. Auch bei der Programmierung rekursiver Unterprogramme muß es eine Abbruchbedingung geben, bei der die Rekursion stoppt und kein neuerlicher Selbstaufruf mehr erfolgt. Beim Fehlen einer Abbruchbedingung ruft sich das Unterprogramm so lange selbst auf, bis der Stack-Speicher erschöpft ist. In der Folge kommt es zu einer Fehlermeldung, dem sogenannten Stack-Overflow. Wird ein rekursives Unterprogramm aufgerufen, erfolgt ein Push-Vorgang und Daten werden auf den Stack gelegt. Dann werden die Befehle bis zum Selbstaufruf ausgeführt. Dies wird „rekursiver Aufstieg“ genannt. Ist die Abbruchbedingung noch nicht erreicht, erfolgt ein Selbstaufruf. Erneut werden Daten auf dem Stack abgelegt. So entwickelt sich Schritt für Schritt eine Datenstruktur auf dem Stack. Bis jetzt wurde nur der rekursive Aufstieg ausgeführt. Tritt jedoch die Abbruchbedingung in Kraft, erfolgt der „rekursive Abstieg“, bei dem die Befehle nach dem Selbstaufruf ausgeführt werden. Nach Beendigung des Unterprogrammes werden Daten vom Stack geholt. Es erfolgt ein schrittweises Auflösen der zuvor gebildeten Datenstruktur. Der rekursive Abstieg endet mit dem Rücksprung ins Hauptprogramm. Die Anzahl der Selbstaufrufe nennt man „Rekursionstiefe.“ Folgendes Beispielprogramm soll zur Veranschaulichung des Rekursionsablaufes dienen: program rekursion01; uses crt; var i : integer;
procedure zaehl(von:integer); {rekursive Prozedur mit dem Parameter von} begin 12143brl86ezl6t write(von,' '); {Variable von am Bildschirm ausgeben - Rekursionsaufstieg} if von>0 then zaehl(von-1); {Abbruchbedingung und Selbstaufruf} write(von,' '); {Variable von am Bildschirm ausgeben-Rekursionsabstieg} end; rz143b2186ezzl
begin 12143brl86ezl6t clrscr; write('Rekursionstiefe: '); readln(i); zaehl(i); {erstmaliger Aufruf mit dem zuvor eingegebenen Wert i} readln; clrscr; end. Dieses Beispielprogramm gibt, wenn als Rekursionstiefe 6 eingegeben wurde, Folgendes am Bildschirm aus: 6 5 4 3 2 1 0 0 1 2 3 4 5 6 aufsteigende absteigende Rekursion Um den Rekursionsablauf zu beschreiben, wird nur 3 als Eingabe für die Rekursiontiefe angenommen, damit sich die Länge der Beschreibung in Grenzen hält. Wird die Prozedur zaehl mit dem Wert 3 aufgerufen, so wird zunächst die Zahl Drei am Bildschirm ausgegeben. Anschließend kommt es zu einem Selbstaufruf, da die Rekursionsbedingung erfüllt ist (Drei ist größer als Null). Als Parameter wird der eigene Parameter, um Eins verringert, übergeben. Für den neuen Prozeduraufruf werden neue lokale Variable auf dem Stack abgelegt, die der aufrufenden Prozedur bleiben jedoch auf dem Stack erhalten, da diese noch nicht beendet wurde. Hierauf wird die Zahl Zwei ausgegeben, und es kommt erneut zum Selbstaufruf. Dieser Ablauf setzt sich so lange fort, bis die Prozedur zaehl mit Null als Parameter aufgerufen wird. Auch Null wird am Bildschirm ausgegeben, aber es kommt zu keinem weiteren Selbstaufruf, da die Rekursionsbedingung nicht mehr erfüllt ist (Null ist nicht größer als Null), und der Rekursionsabstieg begin 12143brl86ezl6t nt. Der Programmablauf wird mit dem nächsten Befehl der Prozedur fortgesetzt, und Null wird nochmals am Bildschirm ausgegeben. Dann wird das Unterprogramm beendet, die lokalen Variablen vom Stack entfernt und zur aufrufenden Prozedur zurückgekehrt. Hier hat die Variable von den Wert Eins. Die Zahl Eins wird daher ausgegeben und das Unterprogramm beendet. Wieder werden die lokalen Variablen vom Stack gelöscht und die Programmausführung mit der aufrufenden Prozedur fortgesetzt, in der die Variable von den Wert Zwei besitzt. Nach der Ausgabe der Zahlen Zwei und Drei erfolgt schließlich der Rücksprung ins Hauptprogramm - die Rekursion ist beendet. Bei jedem Aufruf der Prozedur zaehl wird für die Variable von neuer Speicherplatz belegt, sie ist daher jeweils nur auf einer Rekursionstufe gültig, d.h. auf jeder Rekursionsstufe bezeichnet die Variable von eine andere Stelle im Speicher. Um die Push- und Pop-Vorgänge muß sich der Programmierer in Pascal nicht selbst kümmern. Der Stack wird automatisch vom Compiler verwaltet. Um die compilerinterne Verwaltung des Stack zu veranschaulichen, habe ich das obige Programm so verändert, daß nicht nur die Variablenwerte, sondern auch deren Speicheradressen angegeben werden. Außerdem wird die Adresse des Stack vor und nach dem Durchlaufen der Rekursion angezeigt. Den genauen Quellcode kann man dem Anhang entnehmen (A1, „rekursion01tx“). Die Ausgabe des Programms sieht ungefähr so aus:
Vor dem Prozeduraufruf: Stacksegment: 29031 Stackpointer: 16378
von: Wert: 3 Adresse: 29031:16380 Stackpointer: 16372 von: Wert: 2 Adresse: 29031:16374 Stackpointer: 16366 von: Wert: 1 Adresse: 29031:16368 Stackpointer: 16360 von: Wert: 0 Adresse: 29031:16362 Stackpointer: 16354 von: Wert: 0 Adresse: 29031:16362 Stackpointer: 16354 von: Wert: 1 Adresse: 29031:16368 Stackpointer: 16360 von: Wert: 2 Adresse: 29031:16374 Stackpointer: 16366 von: Wert: 3 Adresse: 29031:16380 Stackpointer: 16372
Nach dem Prozeduraufruf: Stacksegment: 29031 Stackpointer: 16378 Die maximale Größe des Stack beträgt 16 Kilobyte, und er wird von der höchsten bis zur niedrigsten Adresse gefüllt. Daher wird die Adresse des Stack-Endes, auf das der Stackpointer zeigt, mit jedem Prozeduraufruf kleiner. 3 Rekursive Anwendungsprogramme
3.1 Berechnung von Gliedern rekursiver Folgen
Im Folgenden sollen zwei Beispiele näher betrachtet werden: 3.1.1 Die Fakultätsfunktion Die Glieder der Fakultätsfunktion erhält man, indem man alle ganzen Zahlen von 1 bis inklusive der Nummer des zu berechnenden Gliedes multipliziert. So ergibt sich für das dritte Glied zum Beispiel 6, für das fünfte schon 120. Die Fakultätsfunktion läßt sich leicht in der rekursiven Form darstellen: an = n * a(n-1), wobei das erste Glied den Wert Eins besitzt. Auf diesem Bildungsgesetz basiert das folgende Programm: program fakultaet; Muses crt; var i : integer;
function fakt(n : integer) : real; begin 12143brl86ezl6t if n=1 then fakt:=1 else fakt:=fakt(n-1)*n; end; rz143b2186ezzl
begin 12143brl86ezl6t clrscr; writeln(' Fakultätsberechnungsprogramm von Stefan Krywult'); write('n = '); readln(i); writeln(i,'! = ',fakt(i)); readln; clrscr; end. Zunächst gibt der Benützer die Zahl ein, deren Fakultät berechnet werden soll. Sie wird in der Integervariablen i zwischengespeichert und dann der rekursiven Funktion fakt als mit n bezeichneter Parameter übergeben. Nun begin 12143brl86ezl6t nt eine rekursive Schleife: Solange n größer als eins ist, erfolgen Selbstaufrufe, und die Werte, welche die Funktion dabei zurückliefert, werden mit dem jeweils gültigen n multipliziert. Ist n gleich eins, wird der Funktion der Wert Eins zugewiesen. Nun folgt der genaue Ablauf der Rekursion, wenn als Startparameter Drei übergeben wurde: Rekursionsebene: 1 n = 3 n <> 1 fakt := fakt(2)*3 Rekursionsebene: 2 n = 2 n <> 1 fakt := fakt(1)*2 Rekursionsebene: 3 n = 1 n = 1 fakt := 1 Rekursionsebene: 2 n = 2 n <> 1 fakt := 1*2 fakt := 2 Rekursionsebene: 1 n = 3 n <> 1 fakt := 2*3 fakt := 6 => fakt(3) = 6 3.1.2 Die Ackermann-Funktion Wesentlich schwerer ist es, die Ackermann-Funktion zu berechnen. Sie ist eine zweidimensionale Funktion, das heißt, sie benötigt zwei Parameter. Ihr Bildungsgesetz sieht so aus: n + 1 für m = 0, n > 0 A(m,n) = A(m-1, 1) für m > 0, n = 0 A(m-1, A(m, n-1)) für m > 0, n > 0 Doch auch diese Funktion läßt sich fast nach dem selben Schema wie die Fakultätsfunktion programmieren: Zuerst muß ermittelt werden, welcher der drei Fälle vorliegt (bei der Fakultät waren es nur zwei: n=1 oder n>1). Dann erfolgt entweder ein Selbstaufruf mit den entsprechenden Parametern oder die einfache Berechnung A=n+1. Mit folgender Pascalfunktion lassen sich Werte der Ackermann-Funktion berechnen, der restliche Programmcode kann dem Anhang entnommen werden (A1, „ackermann“): function ack(m, n : integer) : integer; begin 12143brl86ezl6t If (m=0) and (n>0) then ack := n+1 If (m>0) and (n=0) then ack := ack(m-1,1); If (m>0) and (n>0) then ack := ack(m-1, ack(m,n-1)); end; rz143b2186ezzl Der Rekursionsablauf ist bei dieser Funktion nur schwer zu durchschauen, da sie sich oftmals sogar zweimal selbst aufruft: Sie ruft sich auf, um den Parameter für den eigentlichen Selbstaufruf zu erhalten. Da die Wahrscheinlichkeit, daß beide Parameter größer als Eins sind, ziemlich groß ist, verzweigt sich die Funktion häufig. Das heißt: Die Funktion ruft sich zweimal auf, diese beiden Funktionen rufen sich wieder zweimal auf und so weiter. Die Zahl der Selbstaufrufe wächst daher stetig. Die rekursive Berechnung der Ackermann-Funktion ist deshalb sehr zeit- und speicherintensiv. Hier wäre es günstiger, die wesentlich schwierigere, aber zeit- und speichersparende iterative Variante zu wählen. Um den komplizierten Ablauf der Funktionsberechnung zu zeigen, folgt nun die Beschreibung des Ablaufes nach dem Funktionsaufruf ack(1, 1): Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, ack(2,0)) Rekursionsebene: 2 m = 2 n = 0 m > 0 n = 0 ack := ack(1, 1) Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0,ack(1,0)) Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := ack(0,1) Rekursionsebene: 5 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2 Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := 2 Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0, 2); Rekursionsebene: 4 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3 Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := 3 Rekursionsebene: 2 m = 2 n = 0 m > 0 n > 0 ack := 3 Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, 3) Rekursionsebene: 2 m = 1 n = 3 m > 0 n > 0 ack := ach(0, ack(1, 2)) Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, ack(1, 1)) Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, ack(1, 0)) Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := ach(0, 1) Rekursionsebene: 6 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2 Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := 2 Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, 2) Rekursionsebene: 5 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3 Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := 3 Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, 3) Rekursionsebene: 4 m = 0 n = 3 m > 0 n > 0 ack := 3 + 1 ack := 4 Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := 4 Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := ach(0, 4) Rekursionsebene: 3 m = 0 n = 4 m = 0 n > 0 ack := 4 +1 ack := 5 Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := 5 Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := 5 3.2 Lösungsfindung durch Zerteilen eines Problems 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 12143brl86ezl6t if z2=0 then ggt:=z1else ggt:=ggt(z2, z1 mod z2); end; rz143b2186ezzl (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 12143brl86ezl6t 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 i<=j then begin 12143brl86ezl6t {4} hilf:=a[i]; a[i]:=a[j]; {5} a[j]:=hilf; inc(i); {6} dec(j); end; rz143b2186ezzl until i>j; {7} if l<j then quicksort(l,j); {8} if r>i then quicksort(i,r); end; rz143b2186ezzl 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 12143brl86ezl6t if anzahl=1 then writeln('Scheibe von ',quelle,' nach ',ziel,'.') else begin 12143brl86ezl6t {1} hanoi(anzahl-1, quelle, ziel, puffer); {2} writeln('Scheibe von ',quelle,' nach ',ziel,'.'); {3} hanoi(anzahl-1,puffer, quelle, ziel); {4} end; rz143b2186ezzl end; rz143b2186ezzl 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. 3.3 Backtracking
Auch hier gibt es vielfältige Anwendungsbeispiele. Die bekannteste Variante dient zum Finden eines oder aller Wege aus einem Labyrinth. 3.2.1 Finden eines Weges aus einem Labyrinth Um den Ausweg aus einem Labyrinth mit dem Computer suchen zu können, muß dieses zuerst in einer geeigneten Form gespeichert werden. Dies ist am besten mit einem zweidimensionalen Zahlenfeld, einem Array of Byte, zu bewerkstelligen. Somit steht für jeden Ort des Labyrinths eine Zahl zur Verfügung, mit deren Hilfe man speichern kann, ob ein Feld zugänglich ist oder nicht und ob es schon betreten wurde. Letzteres ist sehr wichtig, um ein Im-Kreis-Gehen oder gar ein Zurückgehen zu vermeiden, denn dadurch könnte die Lösung nie gefunden werden und die Rekursion liefe endlos, bis es zu einem Stack-Overflow käme. Damit das nicht passiert, kontrolliert das Unterprogramm, ob das Betreten eines Feldes, das an den momentanen Standpunkt grenzt, möglich ist. Im Array wird dieser Versuch gespeichert, und die Prozedur ruft sich selbst mit den neuen Koordinaten des eben betretenen Feldes auf. Dort begin 12143brl86ezl6t nt der Prozeß von neuem. Landet das Programm dabei in einer Sackgasse, kommt es also zu einem Feld, bei dem es keine Möglichkeit eines weiterführenden Schrittes gibt, geht es um ein Feld zurück und überprüft dieses auf weitere Versuchsmöglichkeiten. Werden sie gefunden, geht ihnen der Algorithmus nach, andernfalls geht er um ein weiteres Feld zurück. Man kann entweder nur den erstbesten Weg suchen und dann die Suche abbrechen wie im folgenden Programm, oder man speichert diesen gefundenen Weg und sucht so lange, bis alle Versuchsmöglichkeiten erschöpft sind. Ersteres wurde im folgenden Beispielprogramm realisiert. Um den Suchvorgang zu veranschaulichen, leuchten die Felder, die gerade auf ihre Betretbarkeit überprüft werden, andersfärbig auf. Gelb bedeutet, daß das Feld betretbar ist, braune Felder sind verbaut, dunkelrote wurden bereits besucht.. Der Weg, der während der Suche hellrot leuchtet, wird bei Erreichen eines Ausgangs hellgrün. Weiters sind Verzögerungen in den Algorithmus eingebaut, um die Suche überhaupt nachvollziehen zu können. Das folgende Programm sucht den erstbesten Weg aus dem Labyrinth. program labyrinth; uses crt, tools07; type feld = array[1..20,1..20] of byte; const labnorm : feld = ((2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2), {1} (2,2,2,2,2,0,0,2,2,2,2,2,2,0,0,0,2,2,2,2), (2,2,2,2,2,0,2,2,2,2,2,2,2,2,0,2,2,2,2,2), (2,2,0,0,0,0,2,0,0,0,0,0,0,2,0,2,2,0,2,2), (2,2,2,2,2,0,2,0,2,2,2,2,0,0,0,0,2,0,2,2), (2,2,2,2,2,0,0,0,2,0,2,2,0,2,2,0,2,0,2,2), (2,2,2,2,2,0,2,2,2,0,2,2,0,2,2,0,2,0,2,2), (2,2,2,2,2,0,2,2,2,0,2,2,0,2,2,0,2,0,2,2), (2,2,2,2,2,0,2,2,2,0,0,0,0,0,0,0,2,0,0,3), (3,0,0,0,0,0,2,2,2,0,2,2,2,0,2,2,2,0,2,2), (2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,0,2,2), (2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,2,0,2,2), (2,2,0,0,0,0,2,0,2,2,2,0,2,2,2,0,2,0,2,2), (2,2,0,2,2,0,2,0,2,2,0,0,0,0,0,0,0,0,2,2), (2,2,0,2,2,0,0,0,2,2,0,2,2,2,2,2,0,2,2,2), (2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,0,2,2,2), (2,2,2,2,2,2,2,2,0,0,0,2,2,2,2,2,0,2,2,2), (2,2,2,2,0,0,0,0,0,2,0,0,0,0,2,0,0,2,2,2), (2,2,2,2,2,2,0,2,2,2,2,2,0,2,2,2,2,2,2,2), (2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2,2,2,2));
gefunden : boolean = false; {2}
var lab : feld;
procedure zeigelab; {3} var i, j : integer; begin 12143brl86ezl6t clrscr; for j:= 1 to 20 do begin 12143brl86ezl6t for i:= 1 to 20 do begin 12143brl86ezl6t if (i=10) and (j=10) then begin 12143brl86ezl6t textcolor(9); write(‘ST’); end else case lab[i,j] of 0: write(' '); 1: begin 12143brl86ezl6t if gefunden then textcolor(10) else textcolor(12); write(#219,#219); end; rz143b2186ezzl 2: begin 12143brl86ezl6t textcolor(7); write(#219,#219); end; rz143b2186ezzl 3: begin 12143brl86ezl6t textcolor(10); write('AU'); end; rz143b2186ezzl end; rz143b2186ezzl end; rz143b2186ezzl writeln; end; rz143b2186ezzl end; rz143b2186ezzl
procedure suchweg(x,y:integer); {4} var a,b : integer; begin 12143brl86ezl6t gotoxy(x*2-1,y); {5} textcolor(14); write(#219,#219); delay(333); if not gefunden then begin 12143brl86ezl6t case lab[x,y] of {6} 3: begin 12143brl86ezl6t {7} gefunden:=true; zeigelab; end; rz143b2186ezzl 2: begin 12143brl86ezl6t {8} gotoxy(x*2-1,y); textcolor(6); write(#219,#219);; end; rz143b2186ezzl
1: begin 12143brl86ezl6t {9} gotoxy(x*2-1,y); textcolor(4); write(#219,#219);; end; rz143b2186ezzl
0: begin 12143brl86ezl6t {10} lab[x,y]:=1; {11} zeigelab; {12} if not gefunden then suchweg(x-1,y); {13} if not gefunden then suchweg(x+1,y); if not gefunden then suchweg(x,y+1); if not gefunden then suchweg(x,y-1); if not gefunden then begin 12143brl86ezl6t zeigelab; delay(333); end; rz143b2186ezzl lab[x,y]:=0; {14} end; rz143b2186ezzl end; rz143b2186ezzl end; rz143b2186ezzl end; rz143b2186ezzl
begin 12143brl86ezl6t clrscr; writeln(' Programm zum Suchen eines Ausweges aus einem Labyrith'); window(20,3,70,25); lab:=labnorm; zeigelab; writeln('Bitte Taste drücken, um einen Ausweg zu zeigen...'); wt; clrscr; suchweg(10,10); wt; window(1,1,80,25); clrscr; end. Zuerst wird das Labyrinth als Konstante definiert {1}. Die Variable gefunden ist ein Flag {2}. Ihr wird der Wert True zugewiesen, wenn bereits ein Ausweg gefunden wurde, anderenfalls hat sie den Wert False. Damit kann auf das Finden des Weges an anderen Stellen des Programmes entsprechend reagiert werden. Die Prozedur zeigelab {3} dient lediglich zum Anzeigen des Labyrinths und des bisher gegangenen Weges. Die rekursive Prozedur suchweg {4} ist für das Finden des Ausweges verantwortlich. Ihr werden die Koordinaten (x und y) des als nächstes zu überprüfenden Feldes als Parameter übergeben. Das Unterprogramm markiert dieses Feld zunächst gelb {5}. Nur wenn noch kein Ausweg gefunden wurde, wird das Feld getestet {6}. Ist das aktuelle Feld ein Ausgang, wird der Flag gefunden auf True gesetzt und es erfolgt kein Selbstaufruf {7}. Befindet sich aber eine Mauer darauf oder {8} oder wurde es bereits betreten {9}, wird es in der entsprechenden Farbe dargestellt. Da dieser Versuch nicht erfolgversprechend ist, werden von diesem Feld keine weiteren Schritte gemacht. Anders liegt der Fall, wenn das aktuelle Feld betretbar ist {10}: Das Feld wird als betreten markiert {11}, die veränderte Position auf dem Bildschirm sichtbar gemacht, und von dort ausgehend werden, wenn noch immer kein Ausweg gefunden wurde, alle vier angrenzenden Felder getestet, das heißt, die Prozedur ruft sich selbst mit den entsprechend veränderten Koordinaten auf {13}. Sind alle Versuche beendet, wird das Feld wied |