Autor |
Beitrag |
Udontknow
      
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 09.12.02 15:11
Hallo allesamt!
Da in letzter Zeit wieder öfters Fragen zu Rekursion kommen, habe ich mir gedacht, dass ich dieses Tutorial (neu-)schreibe.
Was ist Rekursion?
Rekursion bedeutet im Grunde genommen, daß sich eine Prozedur oder Funktion in sich selbst erneut aufruft.
Delphi-Quelltext 1: 2: 3: 4:
| procedure Rekursion; begin Rekursion; end; |
Dies ist eine rekursive Konstruktion. Man bezeichnet so etwas als direkt rekursiv.
Ja, es gibt auch indirekte Rekursionen!  Dies sind Rekursionen über zwei oder mehr Prozeduren, etwa so:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| procedure A; begin B; end;
procedure B; begin A; end; |
Hier ruft A die Prozedur B auf, die wiederum erneut A aufruft.
Wer diese Prozeduren ausführt, wird allerdings nach einiger Zeit mit einer Fehlermeldung begrüsst ("Stack overflow"). Darauf werden wir noch näher eingehen, zunächst genügt es, zu sagen, das die Ursache eine fehlende Abbruchbedingung für die Rekursion ist. Das Programm ist sozusagen dann in einer Endlos-Schleife gefangen, und hätte der PC unendlich viel Speicher, würde tatsächlich genau dieses Phänomen auftreten. Das Programm ruft die Prozedur Rekursion auf, die wiederum ruft noch einmal Rekursion auf, usw. etc. pp.
Nehmen wir mal eine "funktionstüchtige" Prozedur:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7:
| prozedur Tauchen(Tiefe:Integer=0); begin ShowMessage('Tauche ab, Tiefe ist '+IntToStr(Tiefe)+'...'); if Tiefe<5 then Tauchen(Tiefe+1); ShowMessage('Tauche auf, Tiefe ist '+IntToStr(Tiefe)+'...'); end; |
Wer diese Prozedur aufruft, wird feststellen, daß er 10 Dialoge in folgender Reihenfolge aufgeblendet bekommt:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| Tauche ab, Tiefe ist 0... Tauche ab, Tiefe ist 1... Tauche ab, Tiefe ist 2... Tauche ab, Tiefe ist 3... Tauche ab, Tiefe ist 4... Tauche auf, Tiefe ist 4... Tauche auf, Tiefe ist 3... Tauche auf, Tiefe ist 2... Tauche auf, Tiefe ist 1... Tauche auf, Tiefe ist 0... |
Hierbei ist das zunächst verblüffende, dass die Zahl Tiefe hochgezählt wird, anschliessend aber auch wieder sinkt, obwohl im Quelltext nichts von "Tiefe:=Tiefe-1" steht.
Die Lösung dieses Rätsels ist, dass das Programm für jeden Prozedur aufruf sich die lokalen Variablen und Parameter merkt. Wenn ich also in meiner vierten Rekursion "Tiefe:=555" setze, so gilt dieser Wert noch lange nicht für den Prozeduraufruf darüber, dort wäre Tiefe immer noch 2 (da wir bei der ersten Prozedur mit Tiefe=0 beginnen).
In Wirklichkeit wird gar nicht die Tiefe an sich verändert, sondern nur der Parameter Tiefe von verschiedenen Prozeduraufrufen ausgegeben.
Praktische Anwendung
Eine praktische Anwendung der Rekursion wäre z.B. das Auflisten aller Dateien in einem Verzeichnis und dessen Unterverzeichnissen.
Das Auflisten in einem Verzeichnis ist ja relativ leicht durch die Routinen FindFirst und FindNext zu finden.
Hier mal der Code zum Auflisten in ein Memofeld:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| procedure FindFiles(Dir:String); var Rec:TSearchRec; begin if FindFirst(Dir+'\*.*', faAnyFile,Rec)=0 then begin repeat Memo1.Lines.Add(Dir+'\'+Rec.Name); until FindNext(Rec)<>0; Findclose(Rec); end; end; |
Nun müssen wir diese Prozedur so verändern, dass sie die Dateien in Unterverzeichnissen ebenfalls durchgeht. Wir prüfen also bei jedem gefundenen Eintrag in Rec, ob es sich um ein Verzeichnis handelt und rufen in diesem Falle dann unsere Prozedur rekursiv mit einem anderen Parameter auf.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure FindFiles(Dir:String); var Rec:TSearchRec; begin FindFirst(Dir+'\*.*', faAnyFile,Rec); FindNext(Rec);
if FindNext(Rec)=0 then begin repeat Memo1.Lines.Add(Dir+'\'+Rec.Name); if (Rec.Attr and faDirectory = faDirectory) then FindFiles(Dir+'\'+Rec.Name); until FindNext(Rec)<>0; end; Findclose(Rec); end; |
Hierbei ist zu beachten, daß die ersten beiden per FindFirst/FindNext gefundenen Einträge ignoriert werden müssen. Es handelt sich um die "virtuellen" Verzeichnisse "." bzw. "..". Spricht man das Verzeichnis "." an, so landet man wieder im selben Verzeichnis, die Pfade "C:\Programme\Test\.\" und "C:\Programme\Test"
zeigen beide auf dieselbe Location auf der Festplatte.
Das Verzeichnis '..' gibt dagegen das Verzeichnis über dem aktuellen an, "C:\Programme\Test\.." ist also dasselbe wie "C:\Programme".
Würde auf diesen Sachverhalt in der Prozedur nicht eingegangen, käme es zu dem o.g. "Stack Overflow", da sich immer wieder nur auf dasselbe Verzeichnis bezogen würde.
Dieses war der erste Streich, und der zweite kommt... irgendwann.
(Konstruktive) Kritik erwünscht.
Cu,
Udontknow
|
|
Udontknow 
      
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 27.01.03 18:41
Hallo wieder einmal!
Nun kommen wir zu einem Thema, an dem sich schon so manch einer die Zähne ausgebissen hat: Routenplanung. Das betrifft die Planung von Wegen für Fahrzeuge (z.B Geldtransporter), aber auch für Spieleprogrammierer kann die Ermittlung des kürzesten Weges von Punkt A nach Punkt B wichtig sein (ist nicht so toll, wenn die Computergegner immer mit dem Kopf durch die Wand wollen, nur weil sich der Spieler hinter dieser aufhält).
Zu diesem Tutorial habe ich ein Demo-Programm geschrieben, das hier heruntergeladen werden kann. Man sollte Kenntnisse in OOP haben, da hier eigene Klassen / Objekte erstellt und benutzt werden.
Wir benötigen natürlich Informationen über den Raum, in dem wir uns bewegen. Wir müssen eine Art Netz definieren, indem jeder Knoten eine Kreuzung einer Strasse oder eine Gabelung im Labyrinth darstellt. Für jeden Knoten müssen wir wissen, zu welchen anderen Knoten wir von hier aus gelangen können.
Ich habe dafür die zwei Klassen TNetz und TKnoten generiert, die man für solche Zwecke gut gebrauchen kann. Jeder Knoten kann mit anderen Knoten über die Methode VerbindeMitKnoten verbunden werden, es wird, sofern man den optionalen Parameter Interconnect nicht mit False bestückt, auch in die andere Richtung eine Verbindung hergestellt (hierüber könnte man also auch "Einbahnstrassen" definieren).
Begnügen wir uns zunächst mal damit, überhaupt irgendeinen Punkt zu finden. Wie könnte man in einem Labyrinth einen bestimmten Punkt finden? Ein Mensch würde zunächst mal sich einfach immer links halten, und hat damit gute Chancen, das gesamte Labyrinth kennen zu lernen. Natürlich hilft das nicht immer, in manchen Labyrinthen läuft man dann immer im Kreis. Irgendwann merkt ein Mensch aber auch das und läuft nicht mehr links entlang, sondern schlägt einen anderen, intuitiv ausgewählten Weg ein.
Ähnlich wird unser Programm arbeiten. Es wird sich zunächst immer von einem Knoten zum nächsten begeben, indem es die erstbeste Verbindung nimmt.
Die Funktion TKnoten.IstKnotenErreichbar benutzen wir, um einen Weg zu finden. Der Parameter Tiefe zeigt uns innerhalb dieser rekursiven Prozedur, die wievielte Rekursion es ist.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| function TKnoten.IstKnotenErreichbar(Zielknoten:TKnoten;Tiefe:Integer=0); var i:Integer; begin Memo.Lines.Add('Überprüfe Knoten '+IntToStr(Self.ID)); if Knoten=Zielknoten then begin Result:=True; exit; end;
for i:=0 to AnzahlVerbindungen-1 do begin if Verbindungen[i].KnotenErreichbar(ZielKnoten, Tiefe+1) then begin Result:=True; Memo.Lines.Add('Ziel über Knoten '+IntToStr(Self.ID)+' erreichbar.'); exit; end; end; end; |
Starten wir nun das Programm und lassen diese Routine laufen, sehen wir, daß immer wieder zwischen Knoten 0 und Knoten 1 hin und her gesprungen wird. Das Programm ist bei Knoten 0 und findet eine Verbindung zu Knoten 1, das Programm geht dorthin. Dort findet es eine Verbindung zu Knoten 0, und geht also wieder zurück. Wir erhalten eine Endlos-Schleife, die irgendwann in einem Stack-Überlauf endet. Das Programm bewegt sich also im Kreis.
Um zu verhindern, daß das Programm im Labyrinth sich immer im Kreis bewegt, geben wir ihm noch ein Gedächtnis mit: Wir merken uns sämtliche Knoten, die wir schon einmal besucht haben.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40:
| function TKnoten.IstKnotenErreichbar(Zielknoten:TKnoten;Tiefe:Integer=0); var i,j:Integer; var KnotenBereitsBesucht:Boolean; begin Memo.Lines.Add('Überprüfe Knoten '+IntToStr(Self.ID)); if Knoten=Zielknoten then begin Result:=True; exit; end;
BesuchteKnoten.Add(Self);
for i:=0 to AnzahlVerbindungen-1 do begin KnotenBereitsBesucht:=False; for j:=0 to BesuchteKnoten.Count-1 do if TKnoten(BesuchteKnoten[j])=Verbindungen[i] then begin KnotenBereitsBesucht:=True; break; end;
if not KnotenBereitsBesucht then if Verbindungen[i].KnotenErreichbar(ZielKnoten, Tiefe+1) then begin Result:=True; Memo.Lines.Add('Ziel über Knoten '+IntToStr(Self.ID)+' erreichbar.'); exit; end; end;
BesuchteKnoten.Delete(BesuchteKnoten.Count-1); end; |
Das soll es für heute erst einmal gewesen sein.
Cu,
Udontknow
|
|
Thomas_1110
      
Beiträge: 22
Win Vista
Delpi 7 Personal
|
Verfasst: Mo 16.06.03 23:26
Hallo
Zitat: | (Konstruktive) Kritik erwünscht. |
Verzeih mir wenn ich nur eine Frage hab
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure FindFiles(Dir:String); var Rec:TSearchRec; begin FindFirst(Dir+'\*.*', faAnyFile,Rec); FindNext(Rec);
if FindNext(Rec)=0 then begin repeat Memo1.Lines.Add(Dir+'\'+Rec.Name); if (Rec.Attr and faDirectory = faDirectory) then FindFiles(Dir+'\'+Rec.Name); until FindNext(Rec)<>0; end; Findclose(Rec); end; |
Bin noch ziemlich neu in Delphi, und wenn ich das Thema 'Rekursionen' und eben diesen Quelltext richtig verstanden hab, soll die Stelle Findclose(Rec); nur einmal aufgerufen werden und das beim Ende der Rekursion. Hab eben an dieser Passage eine Zeile eingefügt, die mir die Anzahl der gefundenen Dateien anzeigt. Man kann richtig sehen wie die Anzeige hinaufschnellt. Hab ich da einen Denkfehler oder ists ein Fehler meiner DelphiVersion (3 prof.).
Wer schön wenn mir da einer ein bischen auf die Sprünge hilft.
Gruß Thomas
|
|
Udontknow 
      
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Di 17.06.03 09:19
Hallo!
Zitat: | Bin noch ziemlich neu in Delphi, und wenn ich das Thema 'Rekursionen' und eben diesen Quelltext richtig verstanden hab, soll die Stelle Code:
Findclose(Rec);
nur einmal aufgerufen werden und das beim Ende der Rekursion |
Nein, Findclose muss aufgerufen werden, um den bei Aufruf von Findfirst bzw. Findnext durch die lokale Variable Rec belegten Speicher wieder freizugeben.
Das Betonung liegt hier auf lokal. Da wir in jedem rekursiven Aufruf sozusagen eine andere Variable Rec haben, müssen wir auch jedes Mal FindClose dafür aufrufen.
Cu,
Udontknow
|
|
Thomas_1110
      
Beiträge: 22
Win Vista
Delpi 7 Personal
|
Verfasst: Di 17.06.03 17:24
Hallo Udontknow
Danke für die schnelle Antwort.
Heißt das jetzt das nach dieser Zeile die Prozedur bis zum Ende abgearbeitet wird und nicht gleich an den Prozeduranfang springt?
Quelltext 1:
| FindFiles(Dir+'\'+Rec.Name); |
Ganz nebenbei bemerkt find ich dein Tutorial sehr gut
Gruß Thomas
|
|
Brueggendiek
      
Beiträge: 304
Win 98, Win98SE, Win XP Home
D5 Std
|
Verfasst: Mi 18.06.03 01:45
Hallo!
Thomas_1110 hat folgendes geschrieben: | Heißt das jetzt das nach dieser Zeile die Prozedur bis zum Ende abgearbeitet wird und nicht gleich an den Prozeduranfang springt? |
Es wird gar nicht gesprungen!
Der rekursive Aufruf einer Prozedur/Funktion sorgt dafür, daß es eine weitere Instanz der Prozedur gibt, die natürlich eigene lokale Variablen hat.
Es ist dabei völlig egal, ob es sich um direkt rekursive Aufrufe (Prozedur ruft sich selber auf), indirekt rekursive Aufrufe (Prozedur ruft was auf, was dann die Prozedur wieder aufruft) oder "normale" Aufrufe ohne Rekursion handelt: Bei Prozeduraufruf werden die lokalen Variablen und die Parameter belegt und sind für diese Instanz eindeutig.
Gruß
Dietmar Brüggendiek
|
|
Elayla
      
Beiträge: 79
|
Verfasst: Mi 18.06.03 06:44
Nettes Programm, ich wollte das mal mit 100 Knoten testen, nach 30000 Prozedurazfrufen und keinem Ende in Sicht hab ichs aber gelassen 
_________________ Das wahre Ziel des Krieges ist der Frieden.
Sun Tzu
|
|
Udontknow 
      
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mi 18.06.03 09:29
Unabhängig davon, daß das Programm durchaus noch optimiert werden könnte, empfehle ich, einfach mal die Checkbox "Info" auszuschalten, damit nicht bei jedem Knoten 100 ms gewartet und der Pfad neu gezeichnet wird...
Dann ist es nämlich auch bei grösseren Netzen schnell durchsucht.
Cu,
Udontknow
|
|
F34r0fTh3D4rk
      
Beiträge: 5284
Erhaltene Danke: 27
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: Fr 10.12.04 19:51
bei dem routenplaner kam es vor, dass direkt am zeil vorbeigeschossen wurde.
die such ging direkt am ziel vorbei und machte daneben weiter, woran liegt das ?
Wäre es nicht sinvoll, den umkreis nach dem ziel abzusuchen, da das ziel ja bekannt ist, es soll ja nur der kürzeste weg gefunden werden. dann würde man in richtug des zieles suchen und nicht alle wege drumrum 
|
|
Udontknow 
      
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Fr 10.12.04 23:21
Was heisst am Ziel vorbei? Der Zielknoten wurde nicht besucht, oder?
Es ist eben so, daß der Algo, so wie er jetzt ist, einfach die Verbindungen von einem Knoten der Reihe nach abklappert, ohne sich vorher mit den Richtungen der Verbindungen auseinanderzusetzen. Das ist manchmal auch gar nicht nötig bzw. sinnvoll, wenn es sich beispielsweise um ein Problem handelt, bei denen die einzelnen Knoten keine Punkte im Raum markieren.
Genauso könnte man auch beim Labyrinth argumentieren: Die Knoten repräsentieren zwar Punkte im Raum, aber die Koordinaten des Ziels sind ja gar nicht bekannt, der Ausgang soll ja gefunden werden.
Ausserdem wäre es ja möglich, daß der Knoten, der am anderen Ende des Labyrinths liegt, die einzige Verbindung zum Ausgang auf der anderen Seite hat. Dass das Labyrinth nun die Knotenverbindungen immer nur zu den nächstgelegenen Knoten hat, ist ja nur eine Sache der Netzgenerierung.
Cu,
Udontknow
|
|
F34r0fTh3D4rk
      
Beiträge: 5284
Erhaltene Danke: 27
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: So 12.12.04 13:17
bei einem Routenplaner aber schon, der start und das ziel sind bekannt.
Die Straßen sind die einzigen verbindungen, also wird der kürzeste weg gesucht.
|
|
Udontknow 
      
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: So 12.12.04 15:55
Ja.
Wie ich schon ein paar mal erwähnt hatte, man kann noch vieles optimieren, tu dir keinen Zwang an, es zu tun. Aber es beeinflusst in keinster Weise das eigentliche Ziel dieses Tutorials.
Cu,
Udontknow
|
|
|