Jetzt lerne ich Pascal... Teil 11

Rekursion

Eine Technik, die es nicht nur bei Pascal gibt sondern auch in vielen anderen Programmiersprachen ist die Rekursion. Jedes Problem ist iterativ oder rekursiv lösbar, jedoch ist meist einer der Wege der elegantere. Rekursion bedeutet in Pascal, dass eine Prozedur oder eine Funktion sich selbst wieder aufruft. Das Paradebeispiel ist die Berechnung der Fakultät. Das kann so gesehen:

function Fakultaet(n : integer) : extended;

var i,res : integer;

begin
  res:=1;
  for i:=1 to n do res:=res*i;
  result:=res;
end;

oder rekursiv:

function Fakultaetrek(n : integer) : extended;

var i,res : integer;

begin
  if n=1 then result:=1
  else result:=fakultaetrek(n-1)*n;
end;

Die rekursive Variante ruft sich selbst auf und sagt: "Ich weiss nicht was die Fakultät von n ist aber die von n-1 ist n*Fak(n-1). Bei jedem Aufruf wird n um eins verkleinert. Ist n gleich 1 so wird 1 zurückgegeben - ohne dieses Abbruchkriterium würde dieses Programmstück ewig laufen. Das Abbruchkriterium ist in jedem rekursiven Programmteil notwendig. Das Abbruchkriterium ist ein Kennzeichen einer Rekursion. Das zweite ist es dass die eigene Funktion erneut mit anderen Parametern aufgerufen wird.

Viel besser zur Demonstration ist jedoch die Konvertierung einer Ganzzahl in einen String. Schauen wir uns zuerst einmal die normale Methode dafür an:

function Int2Str(zahl : integer) : string;

var Temp  : string;

begin
   temp:='';
   while zahl>0 do
   begin
     temp:=chr((zahl mod 2)+48)+temp;
     zahl:=zahl div 2;
   end;
   result:=temp;
end;

Diese Vorgehensweise macht eine Zwischenvariable nötig und ist erheblich länger als das rekursive Gegenstück:

function Int2StrRek(zahl : integer) : string;

begin
   if zahl<2 then result:=chr(zahl+48)
   else result:=Int2StrRek(zahl div 2)+chr((zahl mod 2)+48);
end;

Hier ist der Vorteil der Rekursion zu sehen - Der Code wird kürzer und leichter verständlich. Der Preis für die Rekursion: Bei jedem Aufruf einer Funktion wird die Rücksprungadresse und die lokalen Variablen auf den Stack gespeichert. Das kann ganz schön viel sein, wenn eine Funktion große lokale Variablen hat, aber es ist heute nicht mehr der große Einwand gegen die Rekursion. Viele Algorithmen kann man rekursiv sehr einfach implementieren, wie z.B. den Quicksort. Manchmal wäre eine nicht rekursive Vorgehensweise sehr umständlich. Nehmen wir folgendes Beispiel: Sie suchen in einem Verzeichnis auf der Festplatte nach einer Datei, und zwar nicht nur in diesem Verzeichnis, sondern in allen Unterverzeichnissen. Rekursiv ist das ganz einfach : Hole den nächsten Verzeichniseintrag - Ist es ein Verzeichnis, so rufe dich selbst erneut auf mit diesem Verzeichnis als Startverzeichnis. Ist es eine Datei, so vergleiche sie mit der zu suchenden Datei. Wenn Sie identisch ist, so beende dich. Das könnte dann so aussehen:

function Recurse( var Path: string; const Mask: string; var ergebnis : string ): Boolean;

var
    Srec  : TSearchRec;
    Retval: Integer;
    Oldlen: Integer;

begin
  Result := True;
  Oldlen := Length( Path );
  Retval := FindFirst( Path+Mask, faAnyFile, Srec );
  while Retval = 0 do
  begin
    if (Srec.Attr and (faVolumeID)) = 0 then
    begin
      ergebnis:=Path+Srec.name;
    end;
    Retval := FindNext( Srec );
  end;
  FindClose( Srec );
  if not Result then Exit;
  Retval := FindFirst( Path+'*.*', faDirectory, Srec );
  while Retval = 0 do begin
    if (Srec.Attr and faDirectory) <> 0 then
    if (Srec.name <> '.') and (Srec.name <> '..') then
    begin
      Path := Path + Srec.name + '\';
      if not Recurse( Path, Mask,ergebnis ) then
      begin
        Result := False;
        Break;
      end;
      Delete( Path, Oldlen+1, 255 );
    end;
    Retval := FindNext( Srec );
  end;
  FindClose( Srec );
end; { Recurse }

Hier ist die Abbruchbedingung das Finden der Datei im ersten Teil. Danach folgt das Durchsuchen der Verzeichnisse. Man sollte diese Vorgehensweise beibehalten. Wenn man eine falsche Abbruchbedingung wählt, so dass die Rekursion unendlich läuft, bekommt man irgendwann einen Stack Überlauf, wenn man die Warnungen dafür ausschaltet (Compilerschalter {$S-}) kann das Programm abstürzen.

Dieser Text stammt von Bernd Leitenberger
© des Textes: Bernd Leitenberger. Jede Veröffentlichung dieses Textes im Ganzen oder in Auszügen darf nur mit Zustimmung des Urhebers erfolgen.

Kontakt Neues Bücher vom Autor Buchempfehlungen Gästebuch Top 99