Rekursive Verfahren

Vorwort


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, dass Rekursionen dadurch, dass 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, dass 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.



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, muss 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, muss dieses einen festen Wert besitzen, der ebenfalls bei der Definition angegeben werden muss. 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, dass 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 muss 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, dass 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 Parameter fĂŒr das Unterprogramm, die RĂŒcksprungadresse, d.h. die Speicherstelle, an der die ProgrammausfĂŒhrung nach dem Durchlaufen des Unterprogrammes fortgesetzt werden soll, der letzte Inhalt des BP - Registers(), lokale Variablen, die nur im Unterprogramm GĂŒltigkeit haben, etwaige Funktionswerte.
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, dass 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 muss 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
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;

begin
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 beginnt. 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 muss 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, dass 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


Die Anwendungen der rekursiven Unterprogrammtechnik lassen sich in vier verschiedene Gruppen gliedern. Es sei nochmals darauf hingewiesen, dass heute fast alle Programme iterativ programmiert sind, um sie ĂŒbersichtlicher zu gestalten, da die rekursiven Varianten manchmal ein schlechteres Laufzeitverhalten besitzen. Dennoch ist die rekursive Programmierung bei vielen Projekten von großem Vorteil, da sie oft eine leichtere und schnellere Verwirklichung des Programms ermöglicht. Daher werden in diesem Kapitel vier wichtige Einsatzbereiche der rekursiven Unterprogrammtechnik beschrieben und Beispiele dazu gegeben.


3.1 Berechnung von Gliedern rekursiver Folgen


Das wohl naheliegendste Einsatzgebiet ist das Berechnen von Gliedern rekursiver Folgen. Hier bietet sich der Eisatz von rekursiven Funktionen an, die selbst einen Wert annehmen können. Beim Aufruf der Funktion muss ĂŒberprĂŒft werden, ob die als Parameter ĂŒbergebene Nummer des Gliedes Eins ist. Wenn dies der Fall ist, wird der Funktion der Wert fĂŒr a1 ĂŒbergeben und die Funktion beendet. Andernfalls wird der Funktion ein Wert zugewiesen, der aus einer Berechnung mit dem Funktionswert des vorhergehenden Gliedes resultiert, was einen Selbstaufruf mit dem um eins verringerten Parameter zur Folge hat - der Vorgang beginnt von neuem.
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Ă€sst 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;
uses crt;
var i : integer;

function fakt(n : integer) : real;
begin
if n=1 then fakt:=1 else fakt:=fakt(n - 1)*n;
end;

begin
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 beginnt 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Àsst sich fast nach dem selben Schema wie die FakultÀtsfunktion programmieren: Zuerst muss 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
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;

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, dass 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, sodass 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Àsst 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 i<=j then begin {4}
hilf:=a[i];
a[i]:=a[j]; {5}
a[j]:=hilf;
inc(i); {6}
dec(j);
end;
until i>j; {7}
if l if r>i 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, sodass 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 muss 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 muss 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 dass 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, dass 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


Bei dieser Anwendung der Rekursion macht man sich die Eigenschaft des Pascalcompilers zunutze, dass lokale Variablen bei jedem Selbstaufruf neu angelegt werden, die Werte der vorigen Rekursionsebenen aber noch im Speicher vorhanden sind. So ist es möglich, Lösungen nach dem "Trial and Error" - Prinzip zu suchen. Dabei wird immer die selbe Vorgangsweise verwendet: Von einer gegebenen Ausgangsstellung aus wird nach gewissen Regeln ein Lösungsversuch gemacht, der in einer Variablen notiert wird. Dann kommt es zum Selbstaufruf, und ein Lösungsversuch wird gesucht. Ist die Aufgabenstellung bereits erfĂŒllt, wird der Lösungsweg gespeichert und der Suchvorgang abgebrochen, oder es wird weitergesucht, bis alle Versuche erschöpft sind. Wird kein gĂŒltiger Versuch mehr gefunden, ist das Unterprogramm in einer Sackgasse gelandet und wird beendet. Das aufrufende Unterprogramm löscht den Versuch aus der Variablen und sucht eine neue Versuchsmöglichkeit, wobei nie zweimal derselbe Versuch unternommen wird. Das Backtracking endet entweder nach dem Finden der ersten Lösung oder aber nachdem alle möglichen Versuche unternommen worden sind.
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, muss 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 beginnt 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, dass 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
clrscr;
for j:= 1 to 20 do begin
for i:= 1 to 20 do begin
if (i=10) and (j=10) then begin
textcolor(9);
write(‘ST’);
end else case lab[i,j] of
0: write(' ');
1: begin
if gefunden then textcolor(10) else textcolor(12);
write(#219,#219);
end;
2: begin
textcolor(7);
write(#219,#219);
end;
3: begin
textcolor(10);
write('AU');
end;
end;
end;
writeln;
end;
end;

procedure suchweg(x,y:integer); {4}
var a,b : integer;
begin
gotoxy(x*2 - 1,y); {5}
textcolor(14);
write(#219,#219);
delay(333);
if not gefunden then begin
case lab[x,y] of {6}
3: begin {7}
gefunden:=true;
zeigelab;
end;
2:begin {8}
gotoxy(x*2 - 1,y);
textcolor(6);
write(#219,#219);;
end;

1:begin {9}
gotoxy(x*2 - 1,y);
textcolor(4);
write(#219,#219);;
end;

0: begin {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
zeigelab;
delay(333);
end;
lab[x,y]:=0; {14}
end;
end;
end;
end;

begin
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 wieder als unbetreten markiert {14}, und die Prozedur endet.
Die Beschreibung des Rekursionsablaufes ist bei diesem Programm Ă€ußerst langwierig und kann wesentlich besser durch das obige Programm veranschaulicht werden.
Die zweite Variante dieses Programms sucht alle Auswege aus dem Labyrinth und findet zusĂ€tzlich den kĂŒrzesten heraus. Diesmal ist kein Flag notwendig, da alle möglichen Felder durchsucht werden mĂŒssen. ZusĂ€tzlich wird ein ZĂ€hler fĂŒr die Anzahl der unternommenen Schritte eingefĂŒhrt, und ein Array vom Typ feld wird global deklariert. Immer, wenn ein Ausweg gefunden wurde, wird er in diesem Array gespeichert, und die notwendige Schrittanzahl wird mit der niedrigsten bisherigen verglichen, und gegebenenfalls wird die aktuelle Schrittzahl zum neuen Minimum. Sowohl auf eine Darstellung als auch auf eine Verzögerung des Suchvorganges wurde bei dieser Version aus GrĂŒnden der Laufzeit verzichtet.
Nach der sehr schnell beendeten Suche werden nacheinander die gefundenen Auswege angezeigt, wobei der kĂŒrzeste gekennzeichnet ist. Da diese Variante der obigen ziemlich Ă€hnlich ist, ist ihr Quellcode nur im Anhang (A4, "labyrinth_alle") abgedruckt.


3.3.2 Suche nach möglichst kurzen Strecken zwischen mehreren Punkten


Eine andere Einsatzmöglichkeit des Backtrackings ist das Suchen nach Verbindungen zweier Orte in einem Ortsnetz. Auch hier kann entweder nur die erstbeste Verbindung oder alle Wege zwischen den beiden Orten gesucht werden. Das Schema des Programmes ist dem vorigen sehr Ă€hnlich: Es werden schrittweise alle Reisemöglichkeiten durchprobiert, bis entweder ein Weg gefunden wurde oder aber alle Möglichkeiten erschöpft sind. Zur Speicherung der LĂ€nge der Straßen zwischen zwei Orten dient abermals ein zweidimensionales Array. Ist die LĂ€nge Null, so ist keine direkte Straßenverbindung vorhanden.
Eine rekursive Prozedur speichert in einem String den bisher gegangenen Weg, ĂŒberprĂŒft, ob der Zielort bereits erreicht wurde und geht zu jedem vom aktuellen Ort aus erreichbaren und noch nicht besuchten Ort weiter. Dies geschieht mit einem Selbstaufruf, sodass der Prozeß von neuem beginnt. Wichtig ist wieder, dass kein Ort zweimal besucht wird, da das Programm sonst im Kreis herum ginge, der Algorithmus nicht abbrĂ€che und das Programm auf Grund eines Stack - Overflows abstĂŒrzte. Folgendes Programm sucht alle möglichen Wege, zeigt sie an und ermittelt den kĂŒrzesten:

program weg;
uses crt, tools07;
const ortanz = 7;
type Tortnetz = array[1..ortanz,1..ortanz] of integer;
const ortnetz : Tortnetz = ( ( 0, 43, 0,12, 0, 54, 0), {1}
( 43, 0,34, 3, 0, 23,32),
( 0, 34, 0, 0, 34, 0, 0),
( 12, 3, 0, 0,92, 11, 0),
( 0, 0,34,92, 0, 12, 0),
( 54,23, 0,11,12, 0, 0),
( 0, 32, 0, 0, 0, 0, 0));

gefunden : integer = 0;

var k : integer;
min, lang : integer;
start, ziel : integer;
weg, kweg : string;

procedure zeigeortsnetz; {2}
var i, j :integer;
begin
writeln(' OrtsabstĂ€nde ( - - - .......keine Straße vorhanden)');
write(' ');
for j:=1 to ortanz do write(' ',i,' ');
writeln;
for i:=1 to ortanz do begin
write(' ',i,' ');
for j:=1 to ortanz do if ortnetz[i,j]=0 then write(' - - - ')
else write(' ',ortnetz[i,j]:3,' ');
writeln;
end;
writeln;
end;

procedure gehezu(ort:integer); {3}
var k : integer;
begin
weg:=weg+chr(48+ort); {4}
if ort=ziel then begin {5}
writeln(weg); {6}
inc(gefunden); {7}
if gefunden mod 10 = 0 then begin
writeln;
write('Weiter mit irgendeiner Taste...');
wt;
clrscr;
end;
if (lang min:=lang;
kweg:=weg;
end;
end
else
begin
for k:=1 to ortanz do {9}
if (ortnetz[ort,k]>0) and (pos(chr(48+k),weg)=0) then begin {10}
lang:=lang+ortnetz[ort,k]; {????} {11}
gehezu(k); {12}
lang:=lang - ortnetz[ort,k]; {13}
end;
end;
weg:=copy(weg,1,length(weg) - 1); {14}
end;

begin
lang:=0;
min:=0;
weg:='';
color(7,0);
clrscr;
writeln(' PROGRAMM ZUM REKURSIVEN SUCHEN DES');
writeln(' KÜRZESTEN WEGES ZWISCHEN ZWEI ORTEN IN EINEM ORTSNETZ');
writeln;
writeln(' programmiert von Stefan Krywult im Zuge seiner Informatikfachbereichsarbeit');
writeln;
zeigeortsnetz;
writeln;
write(' Bitte Startort eingeben: ');
readln(start);
write(' Bitte Zielort eingeben: ');
readln(ziel);
writeln;
write('Suche begint bei Tastendruck...');
wt;
clrscr;
zeigeortsnetz;
window(1,12,80,25);
gehezu(start);
if gefunden> 0 then writeln('KĂŒrzeste von ',gefunden,' Wegen ist ',kweg,' mit ',min,' Wegeinheiten.')
else writeln('Es gibt keinen Weg von Ort ',start,' nach Ort ',ziel,'.');
writeln;
writeln('Programmende bei Tastendruck...');
wt;
color(7,0);
clrscr;
end.

Die LĂ€ngen der Verbindungswege werden als Konstanten in einem zweidimensionalen Feld gespeichert {1}. Die Orte selbst sind durch die Zahlen Eins bis Sieben definiert. Die Prozedur zeigeortsnetz {2} dient zur tabellierten Anzeige dieser Daten. Das Unterprogramm gehezu {3}sucht rekursiv alle möglichen von dem in der Variablen start gespeicherten Ausgangsort ausgehende Wege durch, und gibt diejenigen am Bildschirm aus, die zum in ziel gespeicherten Zielort fĂŒhren. Als Parameter wird die Nummer des als nĂ€chstes zu begehenden Ortes ĂŒbergeben. Beim ersten Aufruf vom Hauptprogramm aus ist dies der Startort.
ZunĂ€chst wird die Nummer des Ortes dem String weg hinzugefĂŒgt {4}, worin der bisher zurĂŒckgelegte Weg gespeichert ist. Wenn der aktuelle Ort bereits der Zielort ist {5}, wird der bisherige Weg am Bildschirm ausgegeben {6} und die Anzahl der gefundenen Wege um eins erhöht {7}. Außerdem wird die aktuelle WeglĂ€nge mit der bisher kĂŒrzesten verglichen und das Minimum gegebenenfals neu gesetzt {8}.
Ist der Zielort jedoch noch nicht erreicht, wird systematisch versucht, alle anderen Orte von der momentanen Position aus zu erreichen{9}. Das ist aber nur dann möglich bzw. sinnvoll, wenn es eine Straße dorthin gibt (der Abstand grĂ¶ĂŸer als Null ist) und der Ort noch nicht zuvor betreten wurde (im String gespeichert ist) {10}. Kann der Ort betreten werden, wird die LĂ€nge der Verbindung des neuen und des momentanen Ortes zur GesamtlĂ€nge des Weges addiert {11} und das Unterprogramm gehezu mit dem neuen Ort als Parameter aufgerufen {12}. Hier beginnt der Vorgang von neuem.
Falls der Algorithmus keine Orte mehr findet, die er vom aktuellen Standpunkt aus erreichen könnte, geht er schrittweise den Weg zurĂŒck, um andere Möglichkeiten auszuprobieren. Deswegen muss die LĂ€nge des letzten WegstĂŒckes nach dem Ausprobieren wieder vom Gesamtweg subtrahiert werden {13}. Am Ende der Prozedur wird die letzte Wegnummer aus dem String weg wieder entfernt, um ihn wieder zugĂ€nglich zu machen {14}.


3.2.3 Das Acht - Damen - Problem


Auch das Acht - Damen - Problem lĂ€sst sich mit einem relativ einfachen rekursiven Programm lösen. Dabei mĂŒssen auf einem Schachbrett acht Damen so aufgestellt werden, dass sie einander nicht schlagen können (bei mehr als acht Damen ist dies nicht mehr möglich).
Zur Speicherung eines Schachbretts im Computer bietet sich wieder ein zweidimensionales Feld an, in dem festgehalten wird, ob ein Feld frei, von einer Dame bedroht oder besetzt ist. Um den Algorithmus schneller zu machen, wird davon ausgegangen, dass in jeder Zeile des Schachbrettes nur eine einzige Dame stehen kann. Andernfalls könnten zwei Damen einander schlagen. Mittels Backtracking wird versucht, schrittweise auf jedes freie und unbedrohte Feld eine Dame zu stellen, bis es entweder nur mehr bedrohte und besetzte Felder gibt oder aber bereits 8 Damen aufgestellt worden sind. Wenn noch Damen aufzustellen sind und dies noch möglich ist, wird die neue Dame positioniert, und auf dem Spielfeld werden die betroffenen Felder markiert, anschließend erfolgt ein Selbstaufruf, bei dem das Spielbrett mit der neuen Situation ĂŒbergeben wird.
Auf jedes unbedrohte freie Feld kann eine neue Dame gesetzt werden, da eine unbedrohte Dame sicher keine andere, bereits vorhandene Dame schlagen kann.
Nun folgt der Quellcode des Programmes, das nur eine Lösung des Acht - Damen - Problems sucht, wobei der Status der Suche auf Wunsch stÀndig angezeigt werden kann:

program acht_damen;
uses crt, tools07;
type Tbrett=array[1..8,1..8] of byte; {1}
var start : Tbrett; {2}
i,ii,verz : integer;
danz, lanz : integer;
gefunden : boolean;

procedure zeigbrett(br:Tbrett); {3}
var j,k:integer;
begin
writeln(' 1 2 3 4 5 6 7 8');
for j:=1 to 8 do begin
for k:=0 to 8 do
if k=0 then write(j,' ') else begin
case br[k,j] of
0: begin textcolor(15); write('O '); end;
1: begin textcolor(12); write('X '); end;
2: begin textcolor(14); write('D '); end;
end;
end;
textcolor(7);
writeln;
end;
writeln;
writeln('O = frei, X = durch Dame bedroht, D = durch Dame besetzt ');
writeln(danz,' Damen sind gesetzt.');
end;

procedure stell_dame(brett:Tbrett); {4}
var ax,ay,b : integer;
test : tbrett; {5}
begin
if (verz>0) and not gefunden then begin {6}
gotoxy(1,1);
zeigbrett(brett);
delay(verz);
end;
if (danz=8) and not gefunden then begin {7}
clrscr;
zeigbrett(brett);
gefunden:=true;
writeln(#7);
wt;
end
else if not gefunden then begin {8}
for ax:=1 to 8 do begin
ay:=danz+1; {9}
if brett[ax,ay]=0 then begin {10}
test:=brett; {11}
test[ax,ay]:=2; {12}
inc(danz); {13}
for b:=1 to 8 do begin {14}
if test[ax,b]=0 then test[ax,b]:=1;
if test[b,ay]=0 then test[b,ay]:=1;
if (ax - b)> 0 then begin
if ((ay - b)> 0) and (test[ax - b,ay - b]=0) then test[ax - b,ay - b]:=1;
if ((ay+b) < 9) and (test[ax - b,ay+b]=0) then test[ax - b,ay+b]:=1;
end;
if (ax+b) < 9 then begin
if ((ay - b)> 0) and (test[ax+b,ay - b]=0) then test[ax+b,ay - b]:=1;
if ((ay+b) < 9) and (test[ax+b,ay+b]=0) then test[ax+b,ay+b]:=1;
end;
end;
stell_dame(test); {15}
dec(danz); {16}
end; {if brett...}
end; {for ax}
end; {else begin}
end; {procedure stell_dame}

begin
clrscr;
writeln(' 8 DAMEN AUF EINEM SCHACHBRETT');
writeln(' ein Programm von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit');
window(2,4,78,24);
gefunden:=false;
write('Verzögerung (z.B.:2/20; 0=keine Darstellung): '); {17}
readln(verz);
clrscr;
writeln('Suche lÀuft...');
for i:=1 to 8 do for ii:=1 to 8 do start[i,ii]:=0; {18}
stell_dame(start); {19}
window(1,1,80,25);
clrscr;
end.


Mit der Type - Anweisung {1} wird der Datentyp TBrett als Array[1..8, 1..8] of byte also als zweidimensionales Zahlenfeld definiert. In Variablen dieses Datentyps soll das Schachbrett gespeichert werden. Es ist nicht notwendig, einen eigenen Datentyp dafĂŒr zu definieren, da anstelle von TBrett auch Array[1..8,1..8] of byte geschrieben werden könnte, was aber wesentlich unĂŒbersichtlicher wĂ€re. Die global deklarierte Variable start ist vom Typ TBrett {2}. Die Prozedur zeigebrett {3} dient zur Anzeige des momentanen Suchfortschrittes und der Lösungen. Das rekursive Unterprogramm stell_dame {4} sucht die Lösung des 8 - Damen - Problems. Als Parameter wird eine Variable vom Typ TBrett ĂŒbergeben, in der die momentane Aufstellung gespeichert ist. Neben einigen anderen Hilfsvariablen wird auch das Feld test deklariert {5}. Wichtig ist, dass Laufvariablen fĂŒr Schleifen immer lokal deklariert werden, da sie nur von einer einzigen Rekursionsstufe aus zugĂ€nglich sein dĂŒrfen.
Wenn noch keine Lösung gefunden wurde, erfolgt, falls gewĂŒnscht, eine Darstellung des Suchfortschrittes {6}. Beim eigentlichen Suchvorgang wird dann zunĂ€chst ĂŒberprĂŒft, ob nicht schon acht Damen auf dem Schachbrett untergebracht sind. Wenn dies der Fall ist, wurde bereits eine Lösung gefunden, und sie wird mit Hilfe der Prozedur zeigebrett angezeigt {7}, dann wird das Flag gefunden gesetzt, wodurch die Suche abgebrochen wird. Anderenfalls {8} wird die nĂ€chste Zeile, in der noch keine Dame steht, durchlaufen und nach freien Feldern durchsucht {9}. Wurde eines entdeckt {10}, wird zuerst das ĂŒbergebene Feld in die Hilfsvariable hilf kopiert {11}. In diese wird die gefundene freie Stelle als von einer Dame besetzt markiert {12}. Nachdem die Anzahl der Damen erhöht wurde {13}, werden im Array hilf auch alle von der neu aufgestellten Dame bedrohten Felder markiert {14}. Dann erfolgt ein Selbstaufruf, wobei als Parameter die Variable hilf, also das alte Feld mit der zusĂ€tzlichen Dame und der von ihr bedrohten Felder, ĂŒbergeben wird {15}.
Danach wird die Anzahl der Damen wieder um eins reduziert {16}. Die Dame muss nicht wieder vom Spielfeld entfernt werden, was sehr aufwendig wĂ€re, da die Aufstellung vor dem HinzufĂŒgen der Dame in der Variable brett noch vorhanden ist. Dies ist der Grund fĂŒr die EinfĂŒhrung der lokalen Hilfsvariablen hilf. Dann werden die anderen Felder der Zeile nach dem gleichen Schema durchprobiert.
Die Rekursion endet, sobald eine Lösung des Problems gefunden wurde. Jeder Versuch endet, sobald keine weitere Dame mehr aufgestellt werden kann oder sobald acht Damen auf dem Brett stehen. Vor dem Aufruf des rekursiven Suchalgorithmus {19} im Hauptprogramm mĂŒssen zuerst die gewĂŒnschte Verzögerung der Suchdarstellung in verz eingegeben {17} und die Elemente des Felds start, das beim ersten Aufruf des Unterprogrammes stell_dame ĂŒbergeben wird, durch Zuweisen des Wertes Null initialisiert werden, da das Brett zu Beginn ja noch leer ist {18}.


3.3.4 Rekursives Durchsuchen des Verzeichnisbaumes nach Dateien


Eine etwas andere Art des Backtracking wird in der Praxis oft fĂŒr das Suchen von Dateien in einem Verzeichnisbaum eingesetzt: Einer rekursive Prozedur wird ein Verzeichnis als Parameter ĂŒbergeben. Sie durchsucht dieses zuerst nach dem eingegebenen Dateinamen und gibt gegebenenfalls passende aus. Anschließend wird das Verzeichnis nach Unterverzeichnissen durchsucht. Wird eines gefunden, ruft sich die Prozedur selbst auf, wobei sie als Parameter dessen Pfad ĂŒbergibt. Danach wird mit dem Unterverzeichnis genauso verfahren wie mit dem Überverzeichnis. Der Suchvorgang bricht ab, sobald alle Unterverzeichnisse des vom Startverzeichnis ausgehenden Verzeichnisbaumes durchsucht worden sind.
Folgendes Programm verfĂ€hrt nach dem oben beschriebenen Prinzip. Wegen der Übersichtlichkeit wurde der Arbeitsgang auf drei Prozeduren aufgeteilt:

program rekfsuch;
uses crt,dos,tools07;
const abbruch : boolean = false; {1}
var anz : integer;
s : string;
ch : char;
suchstring : string;
suchpfad : string;

procedure ausgabe(erg : string; a:byte); {2}
begin
inc(anz);
if odd(anz) then textcolor(7) else textcolor(3);
write(anz,': ',erg);
gotoxy(60,wherey);
if (a and $01)=$01 then write('RO ') else write(' ');
if (a and $02)=$02 then write('H ') else write(' ');
if (a and $04)=$04 then write('S ') else write(' ');
if (a and $10)=$10 then write('D ') else write(' ');
if (a and $20)=$20 then write('A') else write(' ');
writeln;
textcolor(7);
if anz mod 15 = 0 then begin

writeln;
writeln('RO=Read Only, H=Hidden, S=System, D=Direktory, A=Archiv');
write('Weiter mit Taste (Ende=[Esc]) ...');
repeat until keypressed;
ch:=readkey;
if ch=#27 then abbruch:=true;
if not abbruch then clrscr else gotoxy(1,wherey - 2);
end;
end;

procedure suchdateien(verzeichnis:string); {3}
var files : SearchRec; {4}
begin
if not abbruch then begin
FindFirst(verzeichnis+suchstring,anyfile,files); {5}
while (doserror=0) and not abbruch do begin {6}
if ((files.attr and VolumeID)<>VolumeID)
then ausgabe(verzeichnis+files.name, files.attr); {7}
if keypressed then begin {8}
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(files); {9}
end;
end;
end;

procedure such(verzeichnis:string); {10}
var dirs : SearchRec; {11}
begin
if not abbruch then begin {12}
suchdateien(verzeichnis); {13}
FindFirst(verzeichnis+'*.*',directory,dirs); {14}
while (doserror=0) and not abbruch do begin {15}
if (dirs.attr and directory=directory) {16}
and (dirs.name <>'.')
and (dirs.name <>'..')
then such(verzeichnis+dirs.name+'\');
if keypressed then begin {17}
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(dirs); {18}
end;
end;
end;

begin
color(15,1);
anz:=0;
clrscr;
writeln(' REKURSIVES DATEISUCHPROGRAMM');
writeln(' geschrieben von Stefan Krywult fĂŒr seine Fachbereichsarbeit 1998');
window(3,4,78,24);
color(7,0);
clrscr;
window(5,5,76,23);
write('Suchpfad: ');
readln(suchpfad);
write('Zu suchende Datei oder zu suchendes Verzeichnis: ');
readln(suchstring);
writeln;
writeln('Suche beginnt bei Tastendruck.');
writeln('Ein Abbruch ist jeder Zeit mit [Esc] möglich.');
wt;
clrscr;
such(suchpfad); {19}
writeln;
writeln('RO=Read Only, H=Hidden, S=System, D=Direktory, A=Archiv');
If not abbruch then writeln('In ',suchpfad,' wurde ',suchstring,' ',anz,'mal gefunden.')
else writeln('In ',suchpfad,' wurde ',suchstring,' bis zum Abbruch ',anz,'mal gefunden.');
write('Programm endet bei Tastendruck...');
wt;
window(1,1,80,25);
color(7,0);
clrscr;
end.

Die typisierte Konstante abbruch ist ein Variable vom Typ Boolean, die zu Beginn des Programmes den Wert False besitzt und als Flag verwendet wird {1}. Ist es gesetzt, wird die Suche abgebrochen. Die Prozedur ausgabe gibt den in erg ĂŒbergebenen Datei - oder Verzeichnisnamen mit Pfad und Attributen formatiert am Bildschirm aus {2}. Das Unterprogramm suchdateien {3} durchsucht das in der Variablen verzeichnis ĂŒbergebene Unterverzeichnis nach der zuvor eingegebenen Datei und gibt sie gegebenenfalls mit Hilfe der Prozedur ausgabe aus. Als lokale Variable wird files als SearchRec deklariert. Dieser Variablentyp enthĂ€lt mehrere Datenfelder und ist fĂŒr den Aufruf der Pascalprozeduren FindFirst und FindNext notwendig {4}. Ein Feld dieses Typs enthĂ€lt den Dateinamen, andere die Dateiattribute, die DateigrĂ¶ĂŸe sowie interne Daten, die fĂŒr die Suche notwendig sind und mit denen ihr momentaner Status gespeichert ist.
ZunĂ€chst erfolgt der Aufruf von FindFirst, um die Suche zu initialisieren {5}. Als Argumente werden der Dateiname (nach DOS - Konventionen, das heißt, es sind auch Sternchen erlaubt) mit vollstĂ€ndigem Pfad, nach dem gesucht werden soll, die Dateiattribute, die sie haben mĂŒssen, um gefunden zu werden, und eine Variable vom Typ SearchRec angegeben. FĂŒr die Dateiattribute wurde im obigen Programm die Konstante anyfile angegeben, damit alle Dateien und Verzeichnisse gefunden werden. Wenn die Suche erfolgreich verlaufen ist, enthĂ€lt DosError den Wert Null, im Feld name von files ist die erste gefundene Datei enthalten und es beginnt eine while - Schleife{6}. Nach der Sicherstellung, ob das Suchergebnis nicht der Laufwerksname ist, wird es ausgegeben {7}. Falls die Escape - Taste gedrĂŒckt wurde, wird das Flag abbruch gesetzt {8}, was zum Abbruch der while - Schleife und der gesamten Suche fĂŒhrt. Anderenfalls wird die Suche mit dem Befehl FindNext fortgefĂŒhrt {9}. Die Schleife endet spĂ€testens dann, wenn keine entsprechende Datei mehr gefunden werden konnte und DosError daher einen Wert ungleich Null aufweist.
Die rekursiv programmierte Prozedur such ist Ă€hnlich aufgebaut wie suchdateien, auch ihr wird ein Verzeichnisname als Parameter ĂŒbergeben {10}. Die einzige lokale Variable ist dirs vom Typ SearchRec die fĂŒr FindFirst und FindNext notwendig ist {11}. Die Prozedur wird nur dann weiter ausgefĂŒhrt, wenn das Flag abbruch nicht gesetzt ist {12}, und es wird suchdateien mit dem ĂŒbergebenen Verzeichnis als Parameter aufgerufen, um alle entsprechenden Dateien in diesem Verzeichnis anzuzeigen {13}. Dann wird FindFirst so aufgerufen, dass alle Unterverzeichnisse des ĂŒbergebenen Verzeichnisses gefunden werden {14}. Wieder lĂ€uft eine while - Schleife, so lange, bis keine Unterverzeichnisse mehr gefunden werden können und DosError einen Wert ungleich Null besitzt oder bis das Flag abbruch gesetzt ist {15}. In der Schleife wird zunĂ€chst kontrolliert, ob es sich bei dem Suchergebnis wirklich um ein Unterverzeichnis und nicht um eines der Symbole fĂŒr das gegenwĂ€rtige bzw. das darĂŒberliegende Verzeichnis handelt {16}. (WĂ€re dies der Fall, kĂ€me es beim nachfolgenden Selbstaufruf nĂ€mlich zu einer endlosen Rekursion und somit zum Stack - Overflow.) Anschließend wird wieder ĂŒberprĂŒft, ob die Escape - Taste gedrĂŒckt wurde, und - wenn das der Fall ist - das Flag abbruch gesetzt {17}. Dann wird die Suche mit FindNext fortgesetzt. Die Schleife lĂ€uft, solange bis Escape gedrĂŒckt wird und die Variable abbruch den Wert True besitzt oder keine weiteren Unterverzeichnisse mehr gefunden werden können.
Im Hauptprogramm wird die zu suchende Datei als globale Variable, die in allen Unterprogrammen zugĂ€nglich ist, gespeichert, das Startverzeichnis wird der Prozedur such als Parameter ĂŒbergeben. Diese gibt dann zuerst alle entsprechenden Dateien des ĂŒbergebenen Verzeichnisses aus, durchsucht es dann nach Unterverzeichnissen und ruft sich mit jedem brauchbaren Suchergebnis selbst auf. Da viele Suchen durcheinanderlaufen, ist es wichtig, dass deren Status genau gespeichert wird. Um das braucht sich der Programmierer jedoch nicht zu kĂŒmmern, da ihm die Prozeduren FindFirst und FindNext dies abnehmen.


3.4 Grafische Anwendung der Rekursion


Ein weiteres riesiges Anwendungsgebiet der Rekursion ist die Darstellung von Fraktalen am Computer. Unter diesem Punkt sollen aber nicht wie in Punkt 3.1. einfach rekursive Folgen oder Funktionen dargestellt werden. Vielmehr geht es darum, geometrische Formen nach einer Transformation immer wiederholt darzustellen, sodass sich ein sinnvolles Gebilde ergibt.


3.4.1 Der fraktale Baum


Der fraktale Baum ist ein recht einfaches, aber sehr schönes Beispiel. Der Baumstamm besteht aus der Grundform des Baumes, einem FĂŒnfeck (Abbildung 1). Der BenĂŒtzer definiert das Aussehen dieser Grundform durch die Eingabe des Abstandes der Punkte A und B, sowie zweier Faktoren V1 und V2, die das VerhĂ€ltnis der beiden Höhen H1 und H2 zur LĂ€nge des Vektors AB angeben. Nach dem Zeichnen des Stammes werden rekursiv auf der linken und auf der rechten Seite der Spitze des FĂŒnfecks zwei weitere geometrisch Ă€hnliche gezeichnet. Als Grundlage der Berechnungen dienen die LĂ€nge des Vektors A’linksB‘ beziehungsweise A’rechtsB‘ sowie abermals die VerhĂ€ltnisse V1 und V2. Aus den Angaben wird ein neues FĂŒnfeck als Ast gezeichnet. Zuerst zeichnet das Programm die linke Seite, wobei es so lange fortfĂ€hrt, bis die zuvor eingegebene Rekursionstiefe erreicht worden ist. Dann wird der Vorgang abgebrochen, und es werden, stufenweise vom Ă€ußersten Ast zurĂŒckgehend, auch die rechten Äste gezeichnet.
Abschließend soll noch die Berechnung der einzelnen Punkte erlĂ€utert werden: Auf den Vektor AB werden drei Normale aufgestellt, zwei davon in dessen Begrenzungspunkten mit der LĂ€nge |AB|* V1 und eine in dessen Halbierungspunkt mit der LĂ€nge |AB|* V2. Somit erhĂ€lt man das gewĂŒnschte FĂŒnfeck, dessen Äste nun durch einen zweifachen Selbstaufruf der Prozedur mit den Begrenzungspunkten der schrĂ€gen Seiten erzeugt werden. Das folgende Programm arbeitet nach dem eben erklĂ€rten Prinzip:


program rekursiver_baum;
uses crt, graph, tools07, grtools2;
var s : integer;
v1, v2 : real; {1}
aa, bb : pointtype; {2}
sstufe : integer; {3}
verz : integer; {4}
ch : char;

procedure baum(a, b : pointtype; stufe : integer); {5}
var p : array[1..6] of pointtype; {6}
xd, yd : real; {7}
begin
if stufe>0 then begin {8}
delay(verz); {9}
xd:=b.x - a.x; {10}
yd:=b.y - a.y;
p[1]:=a; {11}
p[2].x:=a.x+round(v1*yd);
p[2].y:=a.y - round(v1*xd);
p[3].x:=a.x+round(xd/2)+round(v2*yd);
p[3].y:=a.y+round(yd/2) - round(v2*xd);
p[4].x:=b.x+round(v1*yd);
p[4].y:=b.y - round(v1*xd);
p[5]:=b;
p[6]:=a;
fillpoly(6,p); {12}
dec(stufe); {13}
baum(p[2],p[3],stufe); {14}
baum(p[3],p[4],stufe); {15}
end;
end;

begin
repeat
clrscr;
writeln(' REKURSIVER GRAFIKBAUM NACH PROF. HERBERT PAUKERT');
writeln(' programmiert von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit 1998');
writeln;
write('Baumhöhe (z.B: 30) : '); {16}
readln(s);
write('Seitliches HöhenverhÀltnis (z.B: 2) : ');
readln(v1);
write('mittleres HöhenverhÀltnis (z.B: 2.5) : ');
readln(v2);
write('Rekursionstiefe (am besten zwischen 3 und 12) :');
readln(sstufe);
write('Verzögerung: ');
readln(verz);
graphinit(0,0);
setbkcolor(0);
setcolor(15);
setfillstyle(3,7);
aa.x:=getmaxx div 2; {17}
aa.y:=getmaxy - getmaxy div 4;
bb.x:=aa.x+s;
bb.y:=aa.y;
line(aa.x,aa.y,bb.x,bb.y);
baum(aa,bb,sstufe); {18}
wt;
closegraph;
write('Nocheinmal ?');
ch:=upcase(readkey);
until ch='N';
clrscr;
end.

Zuerst werden die benötigten Variablen deklariert: In v1 und v2 werden die VerhĂ€ltnisse der Höhen zur Grundlinie in Kommazahlen vom Typ Real gespeichert {1}. Die Variablen aa und bb sind vom Typ PointType, in dem die beiden Koordinaten eines Punktes als ganzzahlige Integerwerte aufbewahrt werden {2}. Sie werden beim Aufruf der rekursiven Prozedur vom Hauptprogramm aus als Startparameter ĂŒbergeben. Die Variable sstufe bestimmt die Anzahl der BaumverĂ€stelungen {3}, und mittels verz kann das Zeichnen des Baumes verzögert werden, um den Vorgang besser beobachten zu können {4}.
Die rekursive Prozedur baum wird mit den Endpunkten der Grundkante des zu zeichnenden FĂŒnfecks in a und b sowie der momentanen Rekursionstiefe in stufe als Parameter aufgerufen {5}. Als lokale Variablen werden das Punktefeld p {6}, in dem das FĂŒnfeck fĂŒr die Ausgabe gespeichert wird, und die Hilfsvariablen xd und yd vom Fließkommazahlen - Typ Real deklariert {7}.
Zuerst wird in der Prozedur ĂŒberprĂŒft, ob stufe den Wert 0 hat und die Rekursion somit bereits beendet werden muss{8}. Ist das nicht der Fall, kommen die weiteren Befehle der Prozedur zur AusfĂŒhrung. Der Programmablauf wird zunĂ€chst um die in verz gespeicherte Anzahl von Millisekunden verzögert{9}, dann wird der Vektor von a nach b berechnet und in den Hilfsvariablen xd und yd zwischengespeichert {10}. Mit dessen Hilfe werden die Punkte des FĂŒnfecks nach dem oben erklĂ€rten Prinzip berechnet und im Punktefeld p gespeichert {11}, damit das FĂŒnfeck mit dem Befehl FillPoly gezeichnet werden kann {12}. Um das zu ermöglichen, ist es notwendig, einen sechsten Punkt mit den selben Koordinaten wie der erste zu speichern und die Anzahl der Punkte neben dem Punktefeld selbst als Parameter zu ĂŒbergeben. Nun ist der Ast fertig gezeichnet, und die momentane Rekursionsstufe kann um 1 verringert werden {13}. Und schließlich erfolgt ein zweifacher Selbstaufruf der Prozedur, wobei die Endpunkte der linken {14} und der rechten {15} Seite der Spitze und die neue, verminderte Rekursionstiefe als Argumente ĂŒbergeben werden.
Im Hauptprogramm werden Baumhöhe, seitliches und mittleres HöhenverhĂ€ltnis, Rekursionstiefe und die LĂ€nge der Verzögerungen zwischen den Zeichenschritten vom BenĂŒtzer eingegeben {16}. Nach der Initialisierung des Grafikmodus werden die Startpunkte des Baumes aa und bb im Bezug auf die Auflösung berechnet {17}, und schließlich wird die Rekursion mit dem Aufruf der Prozedur baum mit diesen Punkten und der zuvor eingegebenen Rekursionstiefe gestartet {18}.


3.4.2 Die Kochkurve








Die Kochkurve, auch Schneeflockenkurve genannt, wird folgendermaßen gebildet (Abbildunge 2): Eine gegebene Strecke wird in drei gleich lange Teile geteilt. Der mittlere wird herausgelöscht, und es wird ĂŒber diesem Abschnitt ein gleichseitiges Dreieck konnstruiert, dessen Basiskante auf dem mittleren StreckenstĂŒck liegt, die aber nicht gezeichnet wird. Das entstandene Gebilde ist ein Zug aus 4 gleich langen Strecken.
Der eben geschilderte Vorgang wird mit jedem dieser StreckenzĂŒge wiederholt, sodass nun eine Figur mit 16 gleich langen Strecken entsteht. Die Anzahl der Wiederholungen kann durch die Rekursionstiefe gesteuert werden. Folgendes Programm zeichnet eine Kochkurve:


program koch;
uses crt,graph,tools07,grtools2;
var rektief : integer; {1}i,j,modus : integer;gr,verz : integer; {2}a,b : pointtype; {3}
verzf : real; {4}

procedure frakt(p1,p2:pointtype; rt:integer; f:real); {5}
var p : array[1..6] of tpoint; {6}v : tpoint; {7}
inti : integer;

begin
if (rt=0) or keypressed then exit; {8}
v.x:=(p2.x - p1.x) div 3; {9}
v.y:=(p2.y - p1.y) div 3;
p[1]:=p1; {10}
p[2].x:=p[1].x+v.x;
p[2].y:=p[1].y+v.y;
p[3].x:=p[1].x+round(v.x*3/2 + f*v.y*sqrt(3)/2);
p[3].y:=p[1].y+round(v.y*3/2 - f*v.x*sqrt(3)/2);
p[4].x:=p[1].x+2*v.x;
p[4].y:=p[1].y+2*v.y;
p[5]:=p2;
p[6]:=p1;
if (modus=1) or (rt=1) then begin {11}
line(p[1].x,p[1].y,p[2].x,p[2].y);
line(p[2].x,p[2].y,p[3].x,p[3].y);
line(p[3].x,p[3].y,p[4].x,p[4].y);
line(p[4].x,p[4].y,p[5].x,p[5].y);
delay(verz);
end;
dec(rt); {12}

for inti :=1 to 4 do frakt(p[inti],p[inti+1],rt,f); {13}
end;

begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der Kochkurve');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln(' frei nach einer Vorlage aus dem Skriptum "FRAKTALE STRUKTUREN" ');
writeln;
repeat
write('Bitte geben Sie die Rekursionstiefe ein (4/6/7 empf.):'); {14}
readln(rektief);
until rektief>=1;
repeat
write('Bitte geben Sie die Verzögerung ein (333/100/10 empf.):');
readln(verz);
until rektief>=0;
write('Bitte geben Sie den Verzerrungsfaktor ein:');
readln(verzf);
write('Bitte geben Sie den Modus ein (1=alle Linien darstellen):');
readln(modus);

clrscr;
graphinit(0,0); {15}
setcolor(1);
cleardevice;
setcolor(15);
a.x:=mmx div 8; {16}
a.y:=mmy div 2;
b.x:=mmx - a.x;
b.y:=mmy - a.y;
frakt(a, b, rektief, verzf); {17}

wt; {18}
closegraph; {19}
clrscr;
end.

Die wichtigsten Variablen in diesem Programm sind rektief {1} und verz {2}, in denen die vom Benutzer eingegebene Rekursionstiefe bzw. die Verzögerung des Darstellungsprozesses gespeichert wird. In den Variablen a und b vom Typ PointType werden die Endpunkte der ursprĂŒnglichen Geraden gespeichert {3}, und verzf speichert einen Verzerrungsfaktor fĂŒr das Zeichnen der Kurve {4}.
Das HerzstĂŒck des Programms, die rekursive Prozedur fakt, berechnet nach dem oben erklĂ€rten Verfahren ĂŒber eine bestimmte Strecke, deren Start - und Endkoordinaten in p1 und p2 ĂŒbergeben werden, den vierteiligen Streckenzug {5}. Auch ein Verzerrungsfaktor f und die momentane Rekursionstiefe werden der Prozedur ĂŒbergeben. In der Hilfsvariablen p, die als ein Feld von Punkten deklariert ist, wird der Streckenzug zwischengespeichert {6}. In der PointType - Variable v {7} wird ein Drittel der ĂŒbergebenen Strecke als Vektor gespeichert, dieser dient als Grundlage fĂŒr die weiteren Berechnungen {9}. Die Befehle der Prozedur werden aber nur dann ausgefĂŒhrt, wenn die gewĂŒnschte Rekursionstiefe noch nicht erreicht, d.h. rt grĂ¶ĂŸer 0 ist und keine Taste gedrĂŒckt wurde {8}. Nach dem Aufstellen des Vektors v {9} folgt die Berechnung der einzelnen Punkte {10}. Der erste besitzt die selben Koordinaten wie der ĂŒbergebene Startpunkt der Strecke, der letzte die selben wie deren Endpunkt. Den zweiten und den vorletzten Punkt des Streckenzuges erhĂ€lt man durch die Addition von v bzw. dem Doppelten von v zum ersten Punkt. Der mittlere Punkt wird errechnet, indem eine Normale mit der LĂ€nge |v|* √3/2 durch den Mittelpunkt der gegebenen Strecke (p1+v*3/2) aufgestellt wird.
Hat der Benutzer 1 als Zeichenmodus eingegeben, wird der Streckenzug bei jedem Prozeduraufruf gezeichnet, sonst nur beim letzten (rt=1) {11}. Nach dem Verringern der momentanen Rekursionstiefe rt um 1 {12} erfolgt in einer Schleife ein vierfacher Selbstaufruf, bei dem die Koordinaten je eines der vier StreckenstĂŒcke als Parameter ĂŒbergeben werden. {13}.
Das Hauptprogramm beschrĂ€nkt sich auf die Eingabe der Rekursionstiefe, der Verzögerung zwischen den Darstellungsschritten und des Verzerrungsfaktors {14}. Danach wird der Grafikmodus initialisiert {15}, eine bildfĂŒllende Strecke in AbhĂ€ngigkeit zur Auflösung errechnet {16}. Schließlich wird die rekursive Prozedur frakt mit den entsprechenden Parametern aufgerufen {17}.
Nach dem Zeichnen der Kochkurve wartet das Programm auf einen Tastendruck {18} und schaltet zurĂŒck in den Textmodus {19}.


3.4.3 Die Sierpinsky - Dreiecke


Das Sierpinsky Dreieck entsteht, wenn die Halbierungspunkte der drei Seiten eines gleichseitigen Dreiecks so mit einander verbunden werden, dass vier Dreiecke entstehen. Mit den drei Ă€ußeren Dreiecken verfĂ€hrt man dann nach dem selben Prinzip. Der ganze Vorgang wird so lange fortgesetzt, bis die gewĂŒnschte Rekursionstiefe erreicht ist (siehe Abbildung 3).





















program sierpins;
uses crt,graph,tools07, grtools2;

var rektief : integer;
gr,verz : integer;
i,j,farbe : integer;


procedure frakt(rt,p1x,p1y,p2x,p2y,p3x,p3y:integer);
begin
if not keypressed then begin
if rt>1 then begin
frakt(rt - 1,(p1x+p3x) div 2,(p1y+p3y) div 2,(p1x+p2x) div 2,(p1y+p2y) div 2,p1x,p1y);
frakt(rt - 1,(p1x+p2x) div 2,(p1y+p2y) div 2,(p2x+p3x) div 2,(p2y+p3y) div 2,p2x,p2y);
frakt(rt - 1,(p2x+p3x) div 2,(p2y+p3y) div 2,(p1x+p3x) div 2,(p1y+p3y) div 2,p3x,p3y);
end;
if farbe=1 then setcolor(rt mod 8+8);
delay(verz);
line(p1x,p1y,p2x,p2y);
line(p2x,p2y,p3x,p3y);
line(p3x,p3y,p1x,p1y);
end;
end;

begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der SIERPINSKY - DREIECKE');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln;
write('Bitte geben Sie die Rekursionstiefe ein (6/7 empf.):');
readln(rektief);
write('Bitte geben Sie die Verzögerung ein: (100/10 empf.):');
readln(verz);

write('Farbdarstellung ? (1=Farbe) :');
readln(farbe);

clrscr;
graphinit(0,0);
cleardevice;
setcolor(mmc);
frakt(rektief,0,0,mmx,0,mmx div 2,mmy);
wt;
closegraph;
clrscr;
end.


Als globale Variablen werden wieder rektief und verz zum Speichern der eingegeben Rekursionstiefe und der Verzögerung verwendet. Die Variable farbe ist ein Flag, in dem festgehalten wird, ob der BenĂŒtzer eine Darstellung mit verschiedenen Farben wĂŒnscht {1}. Die rekursive Prozedur frakt benötigt als Parameter die momentane Rekursionstiefe rt und die Koordinaten der Eckpunkte des Dreiecks {2}. Die Deklaration lokaler Variablen ist diesmal nicht notwendig. Auch die Befehle dieser Prozedur werden nur dann ausgefĂŒhrt, wenn keine Taste gedrĂŒckt wurde {3}, was einen sofortigen Abbruch des Zeichenvorganges durch einen Tastendruck ermöglicht. Ist die gewĂŒnschte Rekursionstiefe noch nicht erreicht und rt daher grĂ¶ĂŸer als 1, ruft sich die Prozedur dreimal selbst auf, wobei die um 1 verringerte Rekursionstiefe und die Eckpunkte der nach dem oben genannten Schema berechneten Dreiecke ĂŒbergeben werden {4}. Ist das Flag farbe auf 1 gesetzt, wird die Zeichenfarbe in AbhĂ€ngigkeit zur Rekursionstiefe neu gesetzt {5}, wodurch erkennbar ist, welche Dreiecke im selben Rekursionsschritt gezeichnet wurden. Nach einer Verzögerung um die in verz eingegeben Anzahl an Millisekunden {6} wird ein Dreieck entsprechend der ĂŒbergebenen Koordinaten gezeichnet {7}. WĂ€hrend die Bildschirmausgabe bei den beiden vorigen Programmen im aufsteigenden Ast der Rekursion stattfand, wird sie hier erst im absteigenden Rekursionsast vollfĂŒhrt, was zur Folge hat, dass nicht zuerst die großen und dann die kleinen Dreiecke, sondern zuerst die kleinen und dann die grĂ¶ĂŸeren gezeichnet werden.
Im Hauptprogramm wird der Benutzer gebeten, die Rekursionstiefe rektief, den Verzögerungsfaktor verz und das Farbflag farb einzugeben {8}. Nach der Initialisierung des Grafikmodus {9} wird die Prozedur frakt mit der Rekursionstiefe und den Koordinaten eines bildschirmfĂŒllenden Dreiecks als Parameter aufgerufen {10}. Das Farbflag farb ist global deklariert und somit im gesamten Programm zugĂ€nglich. Da es sich auch wĂ€hrend der Rekursion nicht verĂ€ndert, muss es nicht als Parameter ĂŒbergeben werden. Nach dem Zeichnen der Dreiecke wartet das Programm auf einen Tastendruck {11} und schaltet danach wieder in den Textmodus. Damit endet das Programm.

Anhang

A.1 Die Quellcodes aller erwÀhnten Programme

program rekursion01;
uses crt;
var i : integer;

procedure zaehl(von:integer);
begin
write(von,' ');
if von>0 then zaehl(von - 1);
write(von,' ');
end;

begin
clrscr;
write('Rekursionstiefe: ');
readln(i);
zaehl(i);
readln;
clrscr;
end.


program rekursion01tx;

uses crt;
var i : integer;
f : text;

procedure zaehl(von:integer);
begin
writeln(f,'von: Wert:',von,' Adresse:',seg(von),':',ofs(von),' Stackpointer: ',sptr);
if von>0 then zaehl(von - 1);
writeln(f,'von: Wert:',von,' Adresse:',seg(von),':',ofs(von),' Stackpointer: ',sptr);
end;

begin
assign(f,'rekprot.txt');
clrscr;
write(' Rekursionstiefe: ');
readln(i);
rewrite(f);
clrscr;
writeln(f,'Vor dem Prozeduraufruf: Stacksegment: ',sseg,' Stackpointer: ',sptr);
writeln(f);
zaehl(i);
writeln(f);
writeln(f,'Nach dem Prozeduraufruf: Stacksegment: ',sseg,' Stackpointer: ',sptr);
writeln('Datei rekprot.txt geschrieben');
close(f);
readln;
clrscr;
end.



program fakultaet;
uses crt;
var i : integer;

function fakt(n : integer) : real;
begin
if n=1 then fakt:=1 else fakt:=fakt(n - 1)*n;
end;

begin
clrscr;
writeln(' FakultÀtsberechnungsprogramm von Stefan Krywult');
write('n = ');
readln(i);
writeln(i,'! = ',fakt(i));
readln;
clrscr;
end.


program ackermann;
uses crt, tools07;
var a, b : integer;

function ack(m, n : integer) : integer;
begin
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;

begin
clrscr;
writeln(' PROGRAMM ZUM BERECHNEN DER ACKERMANNFUNKTION');
writeln(' geschrieben von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit ''98');
writeln;
write('Bitte ersten Parameter eingeben (m<4) : ');
readln(a);
write('Bitte zweiten Parameter eingeben (n<10) : ');
readln(b);
writeln;
writeln('ack(',a,',',b,') = ',ack(a,b));
writeln;
writeln('Weiter mit Tastendruck...');
wt;
clrscr;
end.


program GGT_Berechnung;
uses crt,tools07;
var a, b : longint;

function ggt(z1, z2 :longint): longint;
begin
if z2=0 then ggt:=z1 else ggt:=ggt(z2, z1 mod z2);
end;

begin
clrscr;
writeln(' PROGRAMM ZUM BERECHNEN DES GRÖSSTEN GEMEINSAMEN TEILERS');
writeln(' ZWEIER ZAHLEN NACH EUKLID');
writeln(' geschrieben von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit ''98');
writeln;
write('Bitte erste Zahl eingeben (z1) : ');
readln(a);
write('Bitte zweite Zahl eingeben (z2) : ');
readln(b);
writeln;
writeln('ggt(',a,',',b,') = ',ggt(a,b));
writeln;
writeln('Weiter mit Tastendruck...');
wt;
clrscr;
end.

program sorter;
uses crt,tools07,dos;
type bereich = array[1..16000] of integer;
var feld : bereich;
original : bereich;
anz : integer;
k,j : longint;
h,m,s,hs : word;
z1,z2,z3,z4 : longint;

procedure qsort(var fel:bereich;vo,bi:integer);

procedure sort(von,bis:integer);
var h,l,r,d: integer;
begin
inc(k);
l:=von;
r:=bis;
h:=fel[(r+l) div 2];
repeat
while (fel[l] while (fel[r]>h) do dec(r);
if l<=r then begin
d:=fel[l];
fel[l]:=fel[r];
fel[r]:=d;
inc(l);
dec(r);
inc(j);
end;
until l>=r;
if von if bis>l then sort(l,bis);
end;

begin
k:=0;
j:=0;
sort(vo,bi);
end;

procedure eingabe;
var ze,zi : integer;
begin
writeln;
repeat
writeln('Anzahl der zu sortierenden Zahlen ( 1 < z <= 16000): ');
readln(ze);
until (ze>1) and (ze<=16000);
for zi:=1 to ze do original[zi]:=random(10000);
writeln;
writeln('Eingabe beendet.');
anz:=ze;
end;

procedure ausgabe;
var ze : integer;
begin
for ze:=1 to anz do begin
write(feld[ze]:8);
if ze mod 10 = 0 then delay(2);
end;
end;

procedure msort(var fel:bereich;vo,bi:integer);
var l1,l2,dummy : integer;
begin
for l1:=vo to bi - 1 do begin
for l2:=l1+1 to bi do begin
if fel[l1]>fel[l2] then begin
inc(j);
dummy:=fel[l1];
fel[l1]:=fel[l2];
fel[l2]:=dummy;
end;
end;
end;
end;

begin
randomize;
clrscr;
writeln(' Programm zum Testen der QICKSORT - Routine');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln;
writeln('Sortieren mit MINIMUMSORT:');
eingabe;
writeln;
writeln('Es wurden ',anz,' Elemente eingegeben !');
feld:=original;
writeln;
writeln('Unsortierte Ausgabe erfolgt nach Tastendruck...');
wt;
ausgabe;
writeln;
writeln('Sortieren mit MINIMUMSORT beginnt bei Tastendruck ...');
wt;
clrscr;
j:=0;
k:=1;
writeln('Sortiervorgang mit MINIMUMSORT lÀuft...');
gettime(h,m,s,hs);
z1:=hs+s*100+m*6000+360000*h;
msort(feld,1,anz);
gettime(h,m,s,hs);
z2:=hs+s*100+m*6000+360000*h;
z1:=z2 - z1;
writeln;
writeln('Sortieren beendet.');
writeln('Es erfolgten ',k,' Prozedur - Aufrufe und ',j,' Vertauschungsoperationen.');
write('Benötigte Zeit: ');
write(z1 div 360000);
z1:=z1 - (z1 div 360000)*360000;
write(':',z1 div 6000);
z1:=z1 - (z1 div 6000)*6000;
write(':',z1 div 100);
write(':',z1 mod 100);

writeln;
writeln('Sortierte Ausgabe erfolgt nach Tastendruck...');
wt;
ausgabe;
writeln;

writeln('Weiter mit Taste...');
wt;



clrscr;
writeln(' Programm zum Testen der QICKSORT - Routine');
writeln(' geschrieben von Stefan Krywult in Turbo Pascal 7.0');
writeln;
writeln('Sortieren mit QUICKSORT:');
feld:=original;
writeln;
writeln('Es wurden ',anz,' Elemente eingegeben !');
writeln;
writeln('Unsortierte Ausgabe erfolgt nach Tastendruck...');
wt;
ausgabe;
writeln;
writeln('Sortieren mit QUICKSORT beginnt bei Tastendruck...');
wt;
clrscr;
k:=0;
j:=0;
writeln('Sortieren mit QUICKSORT lÀuft...');
gettime(h,m,s,hs);
z3:=hs+s*100+m*6000+360000*h;
qsort(feld,1,anz);
gettime(h,m,s,hs);
z4:=hs+s*100+m*6000+360000*h;
z3:=z4 - z3;
writeln;
writeln('Sortieren beendet.');
writeln('Es erfolgten ',k,' Prozedur - Aufrufe und ',j,' Vertauschungsoperationen.');
write('Benötigte Zeit: ');
write(z3 div 360000);
z3:=z3 - (z3 div 360000)*360000;
write(':',z3 div 6000);
z3:=z3 - (z3 div 6000)*6000;
write(':',z3 div 100);
write(':',z3 mod 100);
writeln;
writeln('Sortierte Ausgabe erfolgt nach Tastendruck...');
wt;
ausgabe;
writeln;
writeln('Programm beendet.');
writeln('Weiter mit Taste...');
wt;
clrscr;
end.


program Tuerme_von_Hanoi;
uses crt, tools07;
var i,j,k : integer;
schanz : integer;
schritte : integer;

procedure turm(anz,von,uber,nach:integer);
begin
if anz=1 then begin
inc(schritte);
writeln(schritte:6,'.Schritt: Von ',von,' nach ', nach,'.');
if schritte mod 16 = 0 then begin
write('Weiter mit Taste...');
wt;
clrscr;
end;
end
else
begin
turm(anz - 1,von,nach,uber);
inc(schritte);
writeln(schritte:6,'.Schritt: Von ',von,' nach ', nach,'.');
if schritte mod 16 = 0 then begin
write('Weiter mit Taste...');
wt;
clrscr;
end;
turm(anz - 1,uber,von,nach);
end;
end;

procedure bildaufbau;
begin
clrscr;
textbackground(0);
textcolor(15);
writeln(' DIE TÜRME VON HANOI');
writeln(' ====================');
writeln;
writeln(' geschrieben von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit ''97/''98');
writeln;
writeln;
end;

begin
bildaufbau;
window(2,6,78,24);
color(15,1);
clrscr;
window(4,7,76,23);
repeat
write('Bitte geben Sie die Anzahl der zu verwendenden Scheiben ( Z>0 !) ein: ');
readln(schanz);
until schanz>0;
clrscr;
turm(schanz,1,2,3);
wt;
window(1,1,80,25);
color(7,0);
clrscr;
end.


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),
(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
clrscr;
for j:= 1 to 20 do begin
for i:= 1 to 20 do begin
if (i=10) and (j=10) then begin
textcolor(9);
write(‘ST’);
end else case lab[i,j] of
0: write(' ');
1: begin
if gefunden then textcolor(10) else textcolor(12);
write(#219,#219);
end;
2: begin
textcolor(7);
write(#219,#219);
end;
3: begin
textcolor(10);
write('AU');
end;
end;
end;
writeln;
end;
end;

procedure suchweg(x,y:integer); {4}
var a,b : integer;
begin
gotoxy(x*2 - 1,y); {5}
textcolor(14);
write(#219,#219);
delay(333);
if not gefunden then begin
case lab[x,y] of {6}
3: begin {7}
gefunden:=true;
zeigelab;
end;
2:begin {8}
gotoxy(x*2 - 1,y);
textcolor(6);
write(#219,#219);;
end;

1:begin {9}
gotoxy(x*2 - 1,y);
textcolor(4);
write(#219,#219);;
end;

0: begin {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
zeigelab;
delay(333);
end;
lab[x,y]:=0; {14}
end;
end;
end;
end;

begin
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.


program labyrinth_alle;
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),
(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));

var lab : feld;
losungen : array[1..20] of feld;
lanz, i : integer;
schritte : integer;
lschritte : array[1..20] of integer;
min : integer;

procedure zeigelab;
var i, j : integer;
begin
clrscr;
for j:= 1 to 20 do begin
for i:= 1 to 20 do begin
if (i=10) and (j=10) then begin
textcolor(9);
write('ST');
end else case lab[i,j] of
0: write(' ');
1: begin
textcolor(10);
write(#219,#219);
end;
2: begin
textcolor(7);
write(#219,#219);
end;
3: begin
textcolor(10);
write('AU');
end;
end;
end;
writeln;
end;
end;


procedure suchweg(x,y:integer);
var a,b : integer;
begin
case lab[x,y] of
3: begin
inc(lanz);
if lanz <= 20 then begin
losungen[lanz]:=lab;
lschritte[lanz]:=schritte;
if schritte end;
end;
2:;
1:;
0: begin
lab[x,y]:=1;
inc(schritte);
suchweg(x - 1,y);
suchweg(x+1,y);
suchweg(x,y+1);
suchweg(x,y - 1);
dec(schritte);
lab[x,y]:=0;
end;
end;
end;

begin
clrscr;
textcolor(15);
lanz:=0;
min:=1;
writeln(' Programm zum Suchen eines Ausweges aus einem Labyrith');
window(20,3,70,25);
lab:=labnorm;
zeigelab;
writeln('Bitte Enter drĂŒcken, um ALLE Auswege zu zeigen...');
readln;
clrscr;
writeln('Suche lÀuft...');
suchweg(10,10);
clrscr;
writeln('Suche beendet.');
writeln('Es wurden ',lanz,' verschiedene Auswege gefunden.');
writeln('Der kĂŒrzeste ist ',lschritte[min],' Schritte lang.');
writeln;
write('Weiter mit einer Taste...');
wt;
for i:= 1 to lanz do begin
lab:=losungen[i];
zeigelab;
writeln(lschritte[i], ' Schritte bis zum Ausgang.');
if i=min then writeln('Dies ist der kĂŒzeste Ausweg.');
write('Weiter mit einer Taste...');
wt;
clrscr;
end;
window(1,1,80,25);
clrscr;
end.


program weg;
uses crt, tools05;
const ortanz = 7;
type Tortnetz = array[1..ortanz,1..ortanz] of integer;
const ortnetz : Tortnetz = (( 0, 43, 0,12, 0, 54, 0), ( 43, 0,34, 3, 0, 23,32),
( 0, 34, 0, 0, 34, 0, 0),
( 12, 3, 0, 0,92, 11, 0),
( 0, 0,34,92, 0, 12, 0),
( 54,23, 0,11,12, 0, 0),
( 0, 32, 0, 0, 0, 0, 0));

gefunden : integer = 0;

var k : integer;
min, lang : integer;
start, ziel : integer;
weg, kweg : string;

procedure zeigeortsnetz;
var i, j :integer;
begin
writeln(' OrtsabstĂ€nde ( - - - .......keine Straße vorhanden)');
write(' ');
for j:=1 to ortanz do write(' ',i,' ');
writeln;
for i:=1 to ortanz do begin
write(' ',i,' ');
for j:=1 to ortanz do if ortnetz[i,j]=0 then write(' - - - ')
else write(' ',ortnetz[i,j]:3,' ');
writeln;
end;
writeln;
end;

procedure gehezu(ort:integer);
var k : integer;
begin
weg:=weg+chr(48+ort);
if ort=ziel then begin
writeln(weg);
inc(gefunden);
if gefunden mod 10 = 0 then begin
writeln;
write('Weiter mit irgendeiner Taste...');
wt;
clrscr;
end;
if (lang min:=lang;
kweg:=weg;
end;
end
else
begin
for k:=1 to ortanz do
if (ortnetz[ort,k]>0) and (pos(chr(48+k),weg)=0) then
begin
lang:=lang+ortnetz[ort,k];
gehezu(k);
lang:=lang - ortnetz[ort,k];
end;
end;
weg:=copy(weg,1,length(weg) - 1);
end;

begin
lang:=0;
min:=0;
weg:='';
color(7,0);
clrscr;
writeln(' PROGRAMM ZUM REKURSIVEN SUCHEN DES');
writeln(' KÜRZESTEN WEGES ZWISCHEN ZWEI ORTEN IN EINEM ORTSNETZ');
writeln;
writeln(' programmiert von Stefan Krywult im Zuge seiner Informatikfachbereichsarbeit');
writeln;
zeigeortsnetz;
writeln;
write(' Bitte Startort eingeben: ');
readln(start);
write(' Bitte Zielort eingeben: ');
readln(ziel);
writeln;
write('Suche begint bei Tastendruck...');
wt;
clrscr;
zeigeortsnetz;
window(1,12,80,25);
gehezu(start);
if gefunden> 0 then writeln('KĂŒrzeste von ',gefunden,' Wegen ist ',kweg,' mit ',min,' Wegeinheiten.')
else writeln('Es gibt keinen Weg von Ort ',start,' nach Ort ',ziel,'.');
writeln;
writeln('Programmende bei Tastendruck...');
wt;
color(7,0);
clrscr;
end.


program acht_damen;
program acht_damen;
uses crt, tools07;
type Tbrett=array[1..8,1..8] of byte;
var start : Tbrett;
i,ii,verz : integer;
danz, lanz : integer;
gefunden : boolean;

procedure zeigbrett(br:Tbrett);
var j,k:integer;
begin
writeln(' 1 2 3 4 5 6 7 8');
for j:=1 to 8 do begin
for k:=0 to 8 do
if k=0 then write(j,' ') else begin
case br[k,j] of
0: begin textcolor(15); write('O '); end;
1: begin textcolor(12); write('X '); end;
2: begin textcolor(14); write('D '); end;
end;
end;
textcolor(7);
writeln;
end;
writeln;
writeln('O = frei, X = durch Dame bedroht, D = durch Dame besetzt ');
writeln(danz,' Damen sind gesetzt.');
end;

procedure stell_dame(brett:Tbrett); {4}
var ax,ay,b : integer;
test : tbrett; {5}
begin
if (verz>0) and not gefunden then begin
gotoxy(1,1);
zeigbrett(brett);
delay(verz);
end;
if (danz=8) and not gefunden then begin
clrscr;
zeigbrett(brett);
gefunden:=true;
writeln(#7);
wt;
end
else if not gefunden then begin {8}
for ax:=1 to 8 do begin
ay:=danz+1; {9}
if brett[ax,ay]=0 then begin {10}
test:=brett; {11}
test[ax,ay]:=2; {12}
inc(danz); {13}
for b:=1 to 8 do begin {14}
if test[ax,b]=0 then test[ax,b]:=1;
if test[b,ay]=0 then test[b,ay]:=1;
if (ax - b)> 0 then begin
if ((ay - b)> 0) and (test[ax - b,ay - b]=0) then test[ax - b,ay - b]:=1;
if ((ay+b) < 9) and (test[ax - b,ay+b]=0) then test[ax - b,ay+b]:=1;
end;
if (ax+b) < 9 then begin
if ((ay - b)> 0) and (test[ax+b,ay - b]=0) then test[ax+b,ay - b]:=1;
if ((ay+b) < 9) and (test[ax+b,ay+b]=0) then test[ax+b,ay+b]:=1;
end;
end;
stell_dame(test); {15}
dec(danz); {16}
end; {if brett...}
end; {for ax}
end; {else begin}
end; {procedure stell_dame}

begin
clrscr;
writeln(' 8 DAMEN AUF EINEM SCHACHBRETT');
writeln(' ein Programm von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit');
window(2,4,78,24);
gefunden:=false;
write('Verzögerung (z.B.:2/20; 0=keine Darstellung): ');
readln(verz);
clrscr;
writeln('Suche lÀuft...');
for i:=1 to 8 do for ii:=1 to 8 do start[i,ii]:=0;
stell_dame(start); {19}
window(1,1,80,25);
clrscr;
end.



program rekfsuch;
uses crt,dos,tools07;
const abbruch : boolean = false; {1}
var anz : integer;
s : string;
ch : char;
suchstring : string;
suchpfad : string;

procedure ausgabe(erg : string; a:byte);
begin
inc(anz);
if odd(anz) then textcolor(7) else textcolor(3);
write(anz,': ',erg);
gotoxy(60,wherey);
if (a and $01)=$01 then write('RO ') else write(' ');
if (a and $02)=$02 then write('H ') else write(' ');
if (a and $04)=$04 then write('S ') else write(' ');
if (a and $10)=$10 then write('D ') else write(' ');
if (a and $20)=$20 then write('A') else write(' ');
writeln;
textcolor(7);
if anz mod 15 = 0 then begin

writeln;
writeln('RO=Read Only, H=Hidden, S=System, D=Direktory, A=Archiv');
write('Weiter mit Taste (Ende=[Esc]) ...');
repeat until keypressed;
ch:=readkey;
if ch=#27 then abbruch:=true;
if not abbruch then clrscr else gotoxy(1,wherey - 2);
end;
end;

procedure suchdateien(verzeichnis:string);
var files : SearchRec; {4}
begin
if not abbruch then begin
FindFirst(verzeichnis+suchstring,anyfile,files);
while (doserror=0) and not abbruch do begin
if ((files.attr and VolumeID)<>VolumeID) then ausgabe(verzeichnis+files.name, files.attr);
if keypressed then begin {8}
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(files); {9}
end;
end;
end;

procedure such(verzeichnis:string); {10}
var dirs : SearchRec; {11}
begin
if not abbruch then begin {12}
suchdateien(verzeichnis); {13}
FindFirst(verzeichnis+'*.*',directory,dirs);
while (doserror=0) and not abbruch do begin
if (dirs.attr and directory=directory)
and (dirs.name <>'.')
and (dirs.name <>'..')
then such(verzeichnis+dirs.name+'\');
if keypressed then begin {17}
ch:=readkey;
if ch=#27 then abbruch:=true;
end;
findnext(dirs); {18}
end;
end;
end;

begin
color(15,1);
anz:=0;
clrscr;
writeln(' REKURSIVES DATEISUCHPROGRAMM');
writeln(' geschrieben von Stefan Krywult fĂŒr seine Fachbereichsarbeit 1998');
window(3,4,78,24);
color(7,0);
clrscr;
window(5,5,76,23);
write('Suchpfad: ');
readln(suchpfad);
write('Zu suchende Datei oder zu suchendes Verzeichnis: ');
readln(suchstring);
writeln;
writeln('Suche beginnt bei Tastendruck.');
writeln('Ein Abbruch ist jeder Zeit mit [Esc] möglich.');
wt;
clrscr;
such(suchpfad); {19}
writeln;
writeln('RO=Read Only, H=Hidden, S=System, D=Direktory, A=Archiv');
If not abbruch then writeln('In ',suchpfad,' wurde ',suchstring,' ',anz,'mal gefunden.')
else writeln('In ',suchpfad,' wurde ',suchstring,' bis zum Abbruch ',anz,'mal gefunden. ');
write('Programm endet bei Tastendruck...');
wt;
window(1,1,80,25);
color(7,0);
clrscr;
end.


program rekursiver_baum;
uses crt, graph, tools07, grtools2;
var s : integer;
v1, v2 : real;
aa, bb : pointtype;
sstufe : integer;
verz : integer;
ch : char;

procedure baum(a, b : pointtype; stufe : integer);
var p : array[1..6] of pointtype;
xd, yd : real;
begin
if stufe>0 then begin
delay(verz);
xd:=b.x - a.x;
yd:=b.y - a.y;
p[1]:=a;
p[2].x:=a.x+round(v1*yd);
p[2].y:=a.y - round(v1*xd);
p[3].x:=a.x+round(xd/2)+round(v2*yd);
p[3].y:=a.y+round(yd/2) - round(v2*xd);
p[4].x:=b.x+round(v1*yd);
p[4].y:=b.y - round(v1*xd);
p[5]:=b;
p[6]:=a;
fillpoly(6,p);
dec(stufe);
baum(p[2],p[3],stufe);
baum(p[3],p[4],stufe);
end;
end;

begin
repeat
clrscr;
writeln(' REKURSIVER GRAFIKBAUM NACH PROF. HERBERT PAUKERT');
writeln(' programmiert von Stefan Krywult fĂŒr seine Informatikfachbereichsarbeit 1998');
writeln;
write('Baumhöhe (z.B: 30) : ');
readln(s);
write('Seitliches HöhenverhÀltnis (z.B: 2) : ');
readln(v1);
write('mittleres HöhenverhÀltnis (z.B: 2.5) : ');
readln(v2);
write('Rekursionstiefe (am besten zwischen 3 und 12) :');
readln(sstufe);
write('Verzögerung: ');
readln(verz);
graphinit(0,0);
setbkcolor(0);
setcolor(15);
setfillstyle(3,7);
aa.x:=getmaxx div 2;
aa.y:=getmaxy - getmaxy div 4;
bb.x:=aa.x+s;
bb.y:=aa.y;
line(aa.x,aa.y,bb.x,bb.y);
baum(aa,bb,sstufe);
wt;
closegraph;
write('Nocheinmal ?');
ch:=upcase(readkey);
until ch='N';
clrscr;
end.


program koch;
uses crt,graph,tools07,grtools2;
type Tpoint=record
x:integer;
y:integer;
end;

var rektief : integer;
i,j,modus : integer;
gr,verz : integer;
a,b : tpoint;
verzf : real;

procedure frakt(p1,p2:Tpoint; rt:integer; f:real);
var p : array[1..6] of tpoint;
v : tpoint;
inti : integer;
begin
if (rt=0) or keypressed then exit;
v.x:=(p2.x - p1.x) div 3;
v.y:=(p2.y - p1.y) div 3;
p[1]:=p1;
p[2].x:=p[1].x+v.x;
p[2].y:=p[1].y+v.y;
p[3].x:=p[1].x+round(v.x*3/2 + f*v.y*sqrt(3)/2);
p[3].y:=p[1].y+round(v.y*3/2 - f*v.x*sqrt(3)/2);
p[4].x:=p[1].x+2*v.x;
p[4].y:=p[1].y+2*v.y;
p[5]:=p2;
p[6]:=p1;
if (modus=1) or (rt=1) then begin
line(p[1].x,p[1].y,p[2].x,p[2].y);
line(p[2].x,p[2].y,p[3].x,p[3].y);
line(p[3].x,p[3].y,p[4].x,p[4].y);
line(p[4].x,p[4].y,p[5].x,p[5].y);
delay(verz);
end;
dec(rt);

for inti :=1 to 4 do frakt(p[inti],p[inti+1],rt,f);
end;

begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der Kochkurve');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln(' frei nach einer Vorlage aus dem Skriptum "FRAKTALE STRUKTUREN" ');
writeln;
repeat
write('Bitte geben Sie die Rekursionstiefe ein (4/6/7 empf.):');
readln(rektief);
until rektief>=1;
repeat
write('Bitte geben Sie die Verzögerung ein (333/100/10 empf.):');
readln(verz);
until rektief>=0;
write('Bitte geben Sie den Verzerrungsfaktor ein:');
readln(verzf);
write('Bitte geben Sie den Modus ein (1=alle Linien darstellen):');
readln(modus);

clrscr;
graphinit(0,0);
setcolor(1);
cleardevice;
setcolor(15);
a.x:=mmx div 8;
a.y:=mmy div 2;
b.x:=mmx - a.x;
b.y:=mmy - a.y;
frakt(a, b, rektief, verzf);
wt;
closegraph;
clrscr;
end.



program sierpins;
uses crt,graph,tools07, grtools2;
var rektief : integer;
gr,verz : integer;
i,j,farbe : integer;


procedure frakt(rt,p1x,p1y,p2x,p2y,p3x,p3y:integer);
begin
if not keypressed then begin
if rt>1 then begin
frakt(rt - 1,(p1x+p3x) div 2,(p1y+p3y) div 2,(p1x+p2x) div 2,(p1y+p2y) div 2,p1x,p1y);
frakt(rt - 1,(p1x+p2x) div 2,(p1y+p2y) div 2,(p2x+p3x) div 2,(p2y+p3y) div 2,p2x,p2y);
frakt(rt - 1,(p2x+p3x) div 2,(p2y+p3y) div 2,(p1x+p3x) div 2,(p1y+p3y) div 2,p3x,p3y);
end;
if farbe=1 then setcolor(rt mod 8+8);
delay(verz);
line(p1x,p1y,p2x,p2y);
line(p2x,p2y,p3x,p3y);
line(p3x,p3y,p1x,p1y);
end;
end;

begin
clrscr;
writeln(' Programm zum rekursiven Zeichnen der SIERPINSKY - DREIECKE');
writeln(' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit ''98');
writeln;
write('Bitte geben Sie die Rekursionstiefe ein (6/7 empf.):');
readln(rektief);
write('Bitte geben Sie die Verzögerung ein: (100/10 empf.):');
readln(verz);

write('Farbdarstellung ? (1=Farbe) :');
readln(farbe);

clrscr;
graphinit(0,0);
cleardevice;
setcolor(mmc);
frakt(rektief,0,0,mmx,0,mmx div 2,mmy);
wt;
closegraph;
clrscr;
end.

A.2 Bibliographie und Quellennachweis


Die Ideen und das Wissen zu den in dieser Arbeit angegebenen Programmen stammt aus folgender Literatur:

Bartenschlager, Georg / Kopp, Petra, Rekursive Programmierung fĂŒr Pascal, Delphi und C/C++, Franzis - Verlag, Feldkirch, 1997

Paukert, Herbert, Programmieren in Pascal, Programmieren fĂŒr Einsteiger und Fortgeschrittene, MANZ Verlag, Wien, 1995

Paukert, Herbert, Skriptum: Fraktale Strukturen

RĂ€dle, Klaus, Programmieren lernen, Eine EinfĂŒhrung mit Struktogrammen und Programmbeispielen in Turbo Pascal, Carl Hanser Verlag, MĂŒnchen/Wien, 1995

Reichel, Hans - Christian / MĂŒller, Robert / Laub, Josef / Hanisch, GĂŒnter, Lehrbuch der Mathematik, Hölder - Pichler - Tempsky Verlag, Wien, 3.Auflage, 1992, 6.Band


12027 Worte in "deutsch"  als "hilfreich"  bewertet