Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


5. Rekursion



Beseitigung der Rekursion

Doch worin besteht der Zusammenhang zwischen der obigen Implementation (rekursiv) und der Implementation in Kapitel 4 (nichtrekursiv) für die Traversierung eines Baumes? Mit Sicherheit existiert ein enger Zusammenhang, da beide Programme für einen beliebigen gegebenen Baum genau die gleiche Folge von Aufrufen von visit erzeugen. Im vorliegenden Abschnitt untersuchen wir diese Frage im einzelnen, indem wir auf »mechanische« Weise die Rekursion aus dem oben angegebenen Programm für die Preorder-Traversierung entfernen, so daß wir eine nichtrekursive Implementation erhalten.

Das ist die gleiche Aufgabe, vor der ein Compiler steht, wenn er ein rekursives Programm in die Maschinensprache übersetzen muß. Unser Ziel besteht nicht vorrangig darin, Compilierungstechniken zu studieren (obwohl wir einen gewissen Einblick in die Probleme erhalten, die ein Compiler lösen muß), sondern vielmehr in der Untersuchung des Zusammenhangs zwischen rekursiven und nichtrekursiven Implementationen von Algorithmen. Dieses Thema wird im Buch immer wieder eine Rolle spielen.

Wir beginnen mit einer rekursiven Implementation einer Preorder-Traversierung, genau wie oben beschrieben:

    procedure traverse(t: link);
      begin
      if t<>z then
        begin
        visit(t);
        traverse(t^.l);
        traverse(t^.r);
        end
      end;
Zunächst kann der zweite rekursive Aufruf leicht entfernt werden, da ihm kein Code folgt. Jedesmal, wenn der zweite Aufruf ausgeführt werden soll, muß traverse aufgerufen werden (mit dem Argument t^.r); wenn dieser Aufruf dann vollständig ausgeführt wurde, ist der laufende Aufruf von traverse ebenfalls vollständig ausgeführt. Doch die gleiche Folge von Ereignissen kann implementiert werden, wenn man in der folgenden Weise anstelle eines rekursiven Aufrufs einen goto-Aufruf verwendet:

    procedure traverse(t: link);
        label 0,1;
        begin
    0:  if t=z then goto 1;
        visit(t);
        traverse(t^.l);
        t:=t^.r; goto 0;
    1:  end;

Dies ist eine bekannte Methode, die End-Rekursionsbeseitigung (end-recursion removal) genannt wird und die in vielen Compilern implementiert ist. Rekursive Programme sind auf Systemen ohne diese Fähigkeit weniger rentabel, da es zu einer unnötigen und drastischen Verringerung der Effizienz kommen kann, wie dies oben bei factorial und fibonacci der Fall war. In Kapitel 9 untersuchen wir ein wichtiges praktisches Beispiel.

Das Entfernen des anderen rekursiven Aufrufs erfordert mehr Mühe. Im allgemeinen erzeugen die meisten Compiler Code, der für jeden Prozeduraufruf ein und dieselbe Folge von Handlungen durchläuft: »Lege die Werte lokaler Variablen und die Adresse der nächsten Anweisung in einem Stapel ab, setze die Parameterwerte für die Prozedur und gehe zum (goto) Beginn der Prozedur«. Wenn dann eine Prozedur vollständig abgearbeitet ist, muß sie »die Rückkehradresse und die Werte lokaler Variablen aus dem Stapel holen, die Variablen zurücksetzen und gehe zur (goto) Rückkehradresse ausführen«. Natürlich ist der Sachverhalt für die allgemeine Situation, die ein realer Compiler bewältigen muß, noch komplizierter; trotzdem können wir in diesem Sinne den zweiten rekursiven Aufruf aus unserem Programm wie folgt entfernen:

    procedure traverse(t: link);
        label 0,1,2,3;
        begin
    0:  if t=z then goto 1;
        visit(t);
        push(t); t:=t^.l; goto 0;
    3:  t:=t^.r; goto 0;
    1:  if stackempty then goto 2;
        t:=pop; goto 3;
    2:  end;

Es ist nur eine lokale Variable t vorhanden, daher legen wir diese im Stapel ab und springen (goto) zum Anfang. Es gibt nur eine Rückkehradresse, nämlich 3, und sie ist fest, weshalb wir sie nicht im Stapel ablegen. Am Ende der Prozedur entnehmen wir t aus dem Stapel und realisieren einen Sprung zu Rückkehradresse 3. Wenn der Stapel leer ist, kehren wir vom ersten Aufruf zu traverse zurück.

Nun ist zwar die Rekursion beseitigt, doch wir haben eine Vielzahl von goto-Anweisungen vor uns, die ein sehr unübersichtliches Programm bilden. Doch auch diese können »mechanisch« entfernt werden, wodurch man einen Programmabschnitt mit einer klareren Struktur erhält. Zunächst ist der Programmabschnitt zwischen der Marke 3 und der zweiten Anweisung (goto 0) von goto-Anweisungen eingeschlossen und kann einfach verschoben werden, wobei die Marke 3 und die zugehörige goto-Anweisung eliminiert wird. Weiterhin ist der Programmabschnitt zwischen der Marke 0 und der ersten Anweisung (goto 0) weiter nichts als eine while-Schleife. Damit erhalten wir:

    procedure traverse(t: link);
        label 0,2;
        begin
    0:  while t<>z do
          begin
          visit(t);
          push(t^.r); t:=t^.l
          end;
        if stackempty then goto 2;
        t:=pop; goto 0;
    2:  end;
Nun liegt eine weitere Schleife vor, die in eine repeat-Schleife umgewandelt werden kann, indem ein zusätzliches Ablegen (des ursprünglichen Arguments t beim Eintritt in traverse) in den Stapel hinzugefügt wird. Damit erhalten wir ein Programm, in dem keine goto-Anweisungen enthalten sind:

    procedure traverse(t: link);
      begin
      push(t);
      repeat
        t:=pop; 
        while t<>z do
          begin
          visit(t);
          push(t^.r); 
          t:=t^.l
          end;
      until stackempty;
    end;

Diese Variante ist die nichtrekursive »Standardmethode« für die Traversierung eines Baumes. Es ist eine lohnenswerte Übung, vorübergehend zu vergessen, wie dieses Programm hergeleitet wurde, und sich davon zu überzeugen, daß dieses Programm wie angegeben die Preorder-Traversierung eines Baumes realisiert.

Tatsächlich kann die Struktur dieses Programms, die eine Schleife innerhalb einer Schleife aufweist, vereinfacht werden (wofür einige Stapel-Operationen notwendig sind):

    procedure traverse(t: link);
      begin
      push(t);
      repeat
        t:=pop; 
        if t<>z then
          begin
          visit(t);
          push(t^.r); 
          push(t^.l); 
          end;
      until stackempty;
    end;

Dieses Programm hat eine verblüffende Ähnlichkeit mit unserem ursprünglichen rekursiven Preorder-Algorithmus, doch in Wirklichkeit sind die beiden Programme sehr verschieden. Ein wesentlicher Unterschied besteht darin, daß dieses Programm praktisch in jedem Programmiersystem benutzt werden kann, während die rekursive Implementation offensichtlich ein System erfordert, welches Rekursion unterstützt. Doch selbst in einem solchen System ist dieses Verfahren mit Stapel sicherlich weit effizienter.

Schließlich bemerken wir, daß dieses Programm keine Unterbäume im Stapel ablegt. Dies folgt unmittelbar der Entscheidung in der ursprünglichen Implementation, als erste Operation in der rekursiven Prozedur zu testen, ob der Unterbaum Null ist. (Eine andere Möglichkeit wäre, daß die rekursive Implementation t^.l und t^.r testet und den rekursiven Aufruf nur für von Null verschiedene Unterbäume vorsieht.) Wenn man das obige Programm so verändert, daß das Ablegen von Null-Unterbäumen in den Stapel vermieden wird, erhält man den einen Stapel verwendenden Algorithmus für die Preorder-Traversierung aus Kapitel 4.

    procedure traverse(t: link);
      begin
      push(t);
      repeat
        t:=pop; 
        visit(t);
        if t^.r<>z then push(t^.r); 
        if t^.l<>z then push(t^.l); 
      until stackempty;
    end;

Jeder rekursive Algorithmus kann wie oben behandelt werden, um die Rekursion zu beseitigen; tatsächlich ist das eine der wichtigsten Aufgaben eines Compilers. Eine »manuelle« Beseitigung der Rekursion in der hier beschriebenen Weise ist zwar eine komplizierte Aufgabe, führt jedoch oft sowohl zu einer effizienten nichtrekursiven Implementation als auch zu einem besseren Verständnis der Natur der rekursiven Berechnung.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]