Rekursion

Udontknow · Beiträge: 2596 Win7 D2006 WIN32, .NET (C#)

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.

markieren

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! :wink:

Dies sind Rekursionen über zwei oder mehr Prozeduren, etwa so:

markieren

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:

markieren

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:

markieren

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 Prozeduraufruf 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:

markieren

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.

markieren

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
   //Die beiden ersten gefundenen Einträge ignorieren
   FindFirst(Dir+'\*.*', faAnyFile,Rec);
   FindNext(Rec);

   if FindNext(Rec)=0 then
   begin
     repeat
       Memo1.Lines.Add(Dir+'\'+Rec.Name);
       //wenn der Eintrag ein Verzeichnis ist, ebenfalls durchgehen
       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#)

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.

markieren

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));
  //Ist der aktuelle Knoten der gesuchte?
  if Knoten=Zielknoten then
  begin
    Result:=True;
    exit;
  end;

  //Die Verbindungen durchgehen
  for i:=0 to AnzahlVerbindungen-1 do
  begin
    //Wenn dieser Knoten einen Weg zum Ziel darstellt, diesen in die Wegliste aufnehmen
    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.

markieren

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:
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));
  //Ist der aktuelle Knoten der gesuchte?
  if Knoten=Zielknoten then
  begin
    Result:=True;
    exit;
  end;

  //Knoten in die Liste der bereits besuchten Knoten aufnehmen
  BesuchteKnoten.Add(Self);

  //Die Verbindungen durchgehen
  for i:=0 to AnzahlVerbindungen-1 do
  begin
    //Wurde der durch die Verbindung zu erreichende Knoten bereits besucht?
    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
      //Wenn dieser Knoten einen Weg zum Ziel darstellt, diesen in die Wegliste aufnehmen
      if Verbindungen[i].KnotenErreichbar(ZielKnoten, Tiefe+1) then
      begin
      Result:=True;
      Memo.Lines.Add('Ziel über Knoten '+IntToStr(Self.ID)+' erreichbar.');
      exit;
    end;
  end;

  //Diesen Knoten wieder aus der Liste entfernen
  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

Hallo

Zitat:

(Konstruktive) Kritik erwünscht.

Verzeih mir wenn ich nur eine Frage hab :?:

markieren

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 
   //Die beiden ersten gefundenen Einträge ignorieren 
   FindFirst(Dir+'\*.*', faAnyFile,Rec); 
   FindNext(Rec); 

   if FindNext(Rec)=0 then 
   begin 
     repeat 
       Memo1.Lines.Add(Dir+'\'+Rec.Name); 
       //wenn der Eintrag ein Verzeichnis ist, ebenfalls durchgehen 
       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#)

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

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?

markieren

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

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

Nettes Programm, ich wollte das mal mit 100 Knoten testen, nach 30000 Prozedurazfrufen und keinem Ende in Sicht hab ichs aber gelassen :lol:

_________________
Das wahre Ziel des Krieges ist der Frieden.
Sun Tzu

Udontknow · Beiträge: 2596 Win7 D2006 WIN32, .NET (C#)

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... :wink:

Dann ist es nämlich auch bei grösseren Netzen schnell durchsucht.

Cu,
Udontknow

F34r0fTh3D4rk · 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#)

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 · 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#)

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme