Home Computer Pascal Kurs Site Map counter

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.

Zum Thema Computer ist auch von mir ein Buch erschienen. "Computergeschichte(n)" beinhaltet, das was der Titel aussagt: einzelne Episoden aus der Frühzeit des PC. Es sind Episoden aus den Lebensläufen von Ed Roberts, Bill Gates, Steve Jobs, Stephen Wozniak, Gary Kildall, Adam Osborne, Jack Tramiel und Chuck Peddle und wie sie den PC schufen.

Das Buch wird abgerundet durch eine kurze Erklärung der Computertechnik vor dem PC, sowie einer Zusammenfassung was danach geschah, als die Claims abgesteckt waren. Ich habe versucht ein Buch zu schreiben, dass sie dahingehend von anderen Büchern abhebt, dass es nicht nur Geschichte erzählt sondern auch erklärt warum bestimmte Produkte erfolgreich waren, also auf die Technik eingeht.

Die 2014 erschienene zweite Auflage wurde aktualisiert und leicht erweitert. Die umfangreichste Änderung ist ein 60 Seiten starkes Kapitel über Seymour Cray und die von ihm entworfenen Supercomputer. Bedingt durch Preissenkungen bei Neuauflagen ist es mit 19,90 Euro trotz gestiegenem Umfang um 5 Euro billiger als die erste Auflage. Es ist auch als e-Book für 10,99 Euro erschienen.

Mehr über das Buch auf dieser eigenen Seite.

Hier geht's zur Gesamtübersicht meiner Bücher mit direkten Links zum BOD-Buchshop. Die Bücher sind aber auch direkt im Buchhandel bestellbar (da ich über sehr spezielle Themen schreibe, wird man sie wohl kaum in der Auslage finden) und sie sind natürlich in den gängigen Online-Plattformen wie Amazon, Libri, Buecher.de erhältlich.

Sitemap Kontakt Impressum / Datenschutz Neues Hier werben / advertisment here Buchshop Bücher vom Autor Top 99