Robert Sedgewick: Algorithmen

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


5. Rekursion



Teile und Herrsche

Die meisten rekursiven Programme, die wir in diesem Buch betrachten, verwenden zwei rekursive Aufrufe, von denen jeder etwa mit der Hälfte der Eingabewerte operiert. Das ist das sogenannte »Teile-und-Herrsche«-Prinzip für die Entwicklung von Algorithmen (divide and conquer), durch dessen Anwendung oft beachtliche Einsparungen erreicht werden. Programme des Typs »Teile und Herrsche« lassen sich normalerweise nicht auf triviale Schleifen reduzieren, wie das obenstehende Programm für die Fakultäten, da sie zwei rekursive Aufrufe beinhalten; sie führen im Normalfall nicht zu überflüssigen mehrfachen Berechnungen derselben Werte wie im obigen Programm für die Fibonacci-Zahlen, da die Eingabegrößen ohne eine Überlappung aufgeteilt werden.

Als Beispiel wollen wir die Aufgabe betrachten, die Teilstriche für jeden Zoll auf einem Lineal zu zeichnen: Es existieren ein Teilstrich im Punkt 1/2", etwas kürzere Teilstriche in Intervallen von 1/4", noch kürzere Teilstriche in Intervallen von 1/8" usw., wie in Abbildung 5.1 (in vergrößerter Form) dargestellt ist. Wie wir sehen werden, gibt es viele Wege, um diese Aufgabe, die ein Prototyp einfacher Berechnungen des Typs »Teile und Herrsche« ist, zu erfüllen.

Abbildung 5.1
Abbildung 5.1 Ein Lineal.

Wenn die gewünschte Auflösung der Teilung 1/2n" ist, vereinfachen wir die Aufgabe, indem wir alles mit 2n multiplizieren. Die Aufgabe besteht somit darin, einen Teilstrich in jedem Punkt zwischen 0 und 2n zu zeichnen, wobei die Endpunkte nicht inbegriffen sind. Wir nehmen an, daß uns eine Prozedur mark (x , h) zur Verfügung steht, um an der Stelle x einen Teilstrich mit einer Höhe von h Einheiten zu zeichnen. Der mittlere Teilstrich soll n Einheiten hoch sein, die Teilstriche in der Mitte der rechten bzw. linken Hälfte sollen n - 1 Einheiten hoch sein usw. Das folgende rekursive Programm vom Typ »Teile und Herrsche« ist ein sehr einfacher Weg, um dieses Ziel zu erreichen:

    procedure rule(l,r,h: integer);
      var m: integer;
      begin
      if h>0 then
        begin
        m:=(l+r) div 2;
        mark(m,h);
        rule(l,m,h-1);
        rule(m,r,h-1)
        end
      end;

Zum Beispiel würde der Aufruf rule (0, 64, 6) die Abbildung 5.1 in einem entsprechend angepaßten Maßstab liefern. Die dem Verfahren zugrunde liegende Idee ist folgende: Um die Teilstriche in einem Intervall zu zeichnen, wird zuerst der lange Teilstrich in der Mitte ausgeführt. Hierdurch wird das Intervall in zwei gleiche Hälften geteilt. Dann werden unter Anwendung der gleichen Vorgehensweise die (kürzeren) Teilstriche in jeder Hälfte gezeichnet.

Normalerweise empfiehlt es sich, der Abbruchbedingung eines rekursiven Programms besondere Aufmerksamkeit zu widmen; sonst kann der Fall eintreten, daß es nicht abbricht! Im obigen Programm brechen wir ab, wenn die Länge des zu zeichnenden Teilstrichs 0 beträgt. Abbildung 5.2 zeigt den Ablauf im einzelnen, wobei die Abfolge der Prozeduraufrufe und Teilstriche angegeben ist, die sich beim Aufruf rule (0, 8, 3) ergeben. Wir setzen einen Teilstrich in der Mitte und rufen rule für die linke Hälfte auf, verfahren dann ebenso mit der nun entstandenen linken Hälfte und fahren in dieser Weise so lange fort, bis ein Teilstrich der Länge 0 aufgerufen wird. Schließlich kehren wir von rule zurück und markieren die rechten Hälften auf die gleiche Art.

Abbildung 5.2
Abbildung 5.2 Zeichnen eines Lineals.

Für dieses Problem hat die Reihenfolge, in der die Teilstriche gezeichnet werden, keine besondere Bedeutung. Wir hätten den Aufruf mark ebensogut zwischen den beiden rekursiven Aufrufen anordnen können; in diesem Falle würden die Teilstriche für unser Beispiel einfach in der Reihenfolge von links nach rechts gezeichnet, welche Abbildung 5.3 zeigt.

Abbildung 5.3
Abbildung 5.3 Zeichnen eines Lineals (Inorder-Variante).

Die Menge der Teilstriche, die bei diesen beiden Verfahren gezeichnet werden, ist die gleiche, doch die Reihenfolge ist ganz unterschiedlich. Das kann anhand des Baumdiagramms erklärt werden, welches Abbildung 5.4 zeigt. Dieses Diagramm besitzt einen Knoten für jeden Aufruf von rule, der mit den für den betreffenden Aufruf verwendeten Parametern gekennzeichnet ist. Die direkten Nachfolger jedes Knotens entsprechen den sich aus diesem Aufruf ergebenden (rekursiven) Aufrufen von rule zusammen mit ihren Parametern. Ein derartiger Baum kann immer gezeichnet werden, um die dynamischen Eigenschaften einer Anzahl von Prozeduren zu veranschaulichen. Abbildung 5.2 entspricht nun einer Preorder-Traversierung dieses Baumes (wobei das »Besuchen« eines Knotens der Ausführung des Aufrufs von mark entspricht); Abbildung 5.3 entspricht einer Inorder-Traversierung des Baumes.

Abbildung 5.4
Abbildung 5.4 Baum der rekursiven Aufrufe für das Zeichnen eines Lineals.

Im allgemeinen erfordern Algorithmen des Typs »Teile und Herrsche« einige Arbeitsgänge zur Aufspaltung der Eingabeinformation in zwei Teile oder zum Mischen der Ergebnisse der Verarbeitung zweier unabhängiger »aufgelöster« Teile der Eingabeinformation, oder um fortfahren zu können, nachdem die Hälfte der Eingabeinformation verarbeitet worden ist. Dies bedeutet, daß sich vor, nach oder zwischen den beiden rekursiven Aufrufen weiterer Code befinden kann. Wir werden später viele Beispiele solcher Algorithmen finden, insbesondere in den Kapiteln 9, 12, 27, 28 und 41. Wir werden auch auf Algorithmen stoßen, in denen es nicht möglich ist, dem »Teile-und-herrsche«-Prinzip vollständig zu folgen: Möglicherweise besteht die Eingabeinformation aus ungleichen Teilen oder mehr als zwei Teilen, oder die Teile überschneiden sich.

Die Entwicklung nichtrekursiver Algorithmen für diese Aufgabe ist ebenfalls leicht. Das einfachste Verfahren besteht darin, die Teilstriche einfach wie in Abbildung 5.3 der Reihe nach zu zeichnen, jedoch mit Hilfe der direkten Schleife for i:= 1 to N-1 do mark (i,height (i )). Es zeigt sich, daß die hierfür benötigte Funktion height (i) leicht berechnet werden kann: Es ist die Anzahl der Null-Bits am Ende der Binärdarstellung von i. Wie bereits in Kapitel 2 erwähnt und in Kapitel 10 noch ausführlicher erörtert werden wird, ist in Pascal ein Arbeiten mit der Binärdarstellung von Zahlen möglich, auch wenn es nicht immer ganz einfach ist. Es ist sogar möglich, diese Methode direkt von der rekursiven Variante abzuleiten. Dabei bedienen wir uns eines aufwendigen Prozesses zur »Beseitigung der Rekursion«, den wir weiter unten für ein anderes Problem ausführlich untersuchen werden.

Ein weiterer nichtrekursiver Algorithmus, der keiner rekursiven Implementation entspricht, besteht darin, zuerst die kürzesten Teilstriche zu zeichnen, dann die zweitkürzesten usw., wie im folgenden sehr kompakten Programm:

 
    procedure rule(l,r,h: integer);
      var i,j: integer;
      begin
      j:=1;
      for i:=1 to h do
        begin
        for x:=0 to (l+r) div j do 
          mark(l+j+x*(j+j),i);
        j:=j+j;
        end;
      end;

Abbildung 5.5 zeigt, wie dieses Programm die Teilstriche zeichnet. Diese Vorgehensweise entspricht einer Level-Order-Traversierung des Baumes von Abbildung 5.4 (von unten nach oben), sie ist jedoch nicht rekursiv.

Abbildung 5.5
Abbildung 5.5 Zeichnen eines Lineals (nichtrekursive Variante).

Das entspricht der allgemeinen Methode der Entwicklung von Algorithmen, gemäß der wir ein Problem lösen, indem wir zuerst sehr einfache Teilprobleme lösen, dann diese Lösungen kombinieren, um etwas größere Teilprobleme zu lösen usw., bis das gesamte Problem gelöst ist. Diese Herangehensweise könnte »Kombiniere und Herrsche« (combine and conquer) genannt werden. Während es immer möglich ist, für irgendein rekursives Programm eine äquivalente nichtrekursive Implementation zu erhalten, ist es nicht immer möglich, wie in den obigen Beispielen die Reihenfolge der Berechnungen zu ändern; viele rekursive Programme sind davon abhängig, daß die Teilprobleme in einer bestimmten Reihenfolge gelöst werden. Im Gegensatz zu der Top-Down-Orientierung bei »Teile und Herrsche« handelt es sich hierbei um einen Bottom-Up-Ansatz. Wir werden einige Beispiele hierzu kennenlernen, wobei das wichtigste in Kapitel 12 enthalten ist. Eine Verallgemeinerung des Verfahrens wird in Kapitel 42 betrachtet.

Abbildung 5.6 zeigt ein zweidimensionales Muster, das veranschaulichen soll, wie eine einfache rekursive Beschreibung zu einer Berechnung führen kann, die als sehr komplex erscheint. Das Programm, welches das links dargestellte Muster erzeugt, ist tatsächlich nur eine leichte Verallgemeinerung von rule:

    procedure star(x,y,r: integer);
      begin
      if r>0 then
        begin
        star(x-r,y+r,r div 2);
        star(x+r,y+r,r div 2);
        star(x-r,y-r,r div 2);
        star(x+r,y-r,r div 2);
        box(x,y,r);
        end
      end;

Abbildung 5.6
Abbildung 5.6 Ein Fraktal-Stern, gezeichnet mit Kästchen (links) und nur mit Umrissen (rechts).

Das für das Zeichnen benutzte Grundelement ist einfach ein Programm, das ein Quadrat mit der Seitenlänge 2r und mit dem Mittelpunkt in (x, y) zeichnet. Folglich läßt sich das Muster auf der linken Seite von Abbildung 5.6 einfach mit einem rekursiven Programm erzeugen; es bleibt dem Leser überlassen, nach einer rekursiven Methode für das Zeichnen der Umrisse des Musters zu suchen, das rechts abgebildet ist. Das linke Muster läßt sich auch leicht mit einer Bottom-Up-Methode von der Art des in Abbildung 5.5 dargestellten Verfahrens erzeugen: Man zeichne die kleinsten Quadrate, dann die nächstgrößeren usw. Der Leser kann sich auch damit beschäftigen zu versuchen, eine nichtrekursive Methode für das Zeichnen der Figur zu finden.

Rekursiv definierte geometrische Muster wie in Abbildung 5.6 werden manchmal Fraktale (fractals) genannt. Wenn kompliziertere Grundelemente für das Zeichnen und kompliziertere rekursive Aufrufe (insbesondere solche, welche rekursiv definierte Funktionen von reellen Zahlen und in der komplexen Ebene einschließen) benutzt werden, lassen sich Muster von bemerkenswerter Vielfalt und Komplexität entwickeln.


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