Robert Sedgewick: Algorithmen

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


5. Rekursion



Rekurrente Beziehungen

Rekursive Definitionen von Funktionen sind in der Mathematik recht gebräuchlich; den einfachsten Typ, bei dem nur ganzzahlige Argumente auftreten, nennt man rekurrente Beziehungen. Die vielleicht bekannteste derartige Funktion ist die Funktion Fakultät, die mittels der Formel

N! = N*(N-1)!, für N>=1 und 0! = 1

definiert ist.

Diese Formel entspricht unmittelbar dem folgenden einfachen rekursiven Programm:

    function factorial(N: integer): integer;
      begin
      if N=0 
        then factorial:=1 
        else factorial:=N*factorial(N-1);
      end;

Einerseits illustriert dieses Programm die grundlegenden Merkmale eines rekursiven Programms: Es ruft sich selbst auf (mit einem kleineren Wert seines Arguments) und es besitzt eine Abbruchbedingung, in der es das Ergebnis direkt berechnet. Andererseits ist nicht zu übersehen, daß dieses Programm weiter nichts ist als eine ansprechend verpackte for-Schleife, so daß es kaum ein überzeugendes Beispiel für die Leistungsfähigkeit der Rekursion sein dürfte. Auch ist es wichtig, sich daran zu erinnern, daß es ein Programm ist und keine Gleichung. Beispielsweise »funktioniert« weder die obige Gleichung noch das Programm für negative N, doch wenn man dies nicht beachtet, sind beim Programm die negativen Auswirkungen deutlicher sichtbar als bei der Gleichung. Der Aufruf factorial(-1) führt zu einer rekursiven Endlosschleife. Dies ist ein häufig auftretender Programmfehler, der in komplizierteren rekursiven Programmen in einer mehr verdeckten Form enthalten sein kann.

Eine zweite allgemein bekannte rekurrente Beziehung ist die, mit deren Hilfe die Fibonacci-Zahlen definiert sind:

FN = FN-1 + FN-2, für N>= 2, mit F0 = F1 = 1.

Hierdurch wird die Folge

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,...

definiert.

Auch diese rekurrente Beziehung entspricht unmittelbar einem einfachen rekursiven Programm:

    function fibonacci(N: integer): integer;
      begin
      if N<=1 
        then fibonacci:=1 
        else fibonacci:=fibonacci(N-1)+fibonacci(N-2);
      end;
Dies ist ein sogar noch weniger überzeugendes Beispiel von der »Leistungsfähigkeit« der Rekursion; tatsächlich ist es ein überzeugendes Beispiel dafür, daß Rekursion nicht blind benutzt werden sollte, da andernfalls eine äußerst geringe Effizienz die Folge sein kann. Das Problem besteht in diesem Falle darin, daß die rekursiven Aufrufe die Forderung beinhalten, FN-1 und FN-2 unabhängig voneinander zu berechnen, während man in Wirklichkeit sicher FN-2 (und FN-3) verwenden würde, um FN-1 zu berechnen. Es ist übrigens leicht, die exakte Anzahl der Aufrufe der obigen Prozedur fibonacci zu berechnen, die erforderlich sind, um FN zu ermitteln: Die Anzahl der Aufrufe, die zur Berechnung von FN benötigt werden, ist gleich der Summe der Anzahl der Aufrufe, die zur Berechnung von FN-1 benötigt werden, und der Anzahl der Aufrufe, die zur Berechnung von FN-2 benötigt werden, außer bei N = 0 oder N = 1, wo nur ein Aufruf erforderlich ist. Doch dies entspricht genau der rekurrenten Beziehung, durch die die Fibonacci-Zahlen definiert sind; die Anzahl der Aufrufe von fibonacci für die Berechnung von FN beträgt genau FN. Es ist bekannt, daß FN etwa gleich øN ist, ø = 1,61803... das Verhältnis des »Goldenen Schnitts« ist; die schreckliche Wahrheit ist somit, daß obiges Programm einen Algorithmus zur Berechnung der Fibonacci-Zahlen mit exponentiell wachsendem Aufwand darstellt!

Dagegen ist es sehr leicht, FN mit linearem Zeitaufwand auf folgende Weise zu berechnen:

    procedure fibonacci;
      const max=25;
      var i: integer;
          F: array[0..max] of integer;
      begin
      F[0]:=1; F[1]:=1;
      for i:=2 to max do F[i]:=F[i-1]+F[i-2]  
      end;

Dieses Programm berechnet die ersten max Fibonacci-Zahlen unter Verwendung eines Feldes der Größe max. (Da die Zahlen exponentiell wachsen, wird max klein sein.)

Tatsächlich ist diese Technik der Benutzung von Feldern für die Speicherung vorhergehender Ergebnisse das Verfahren, das für die Auswertung rekurrenter Beziehungen gewöhnlich gewählt wird, denn es gibt die Möglichkeit, recht komplizierte Gleichungen in einer einheitlichen und effizienten Weise zu verarbeiten. Rekurrente Beziehungen treten oft dann auf, wenn wir versuchen, Kenngrößen der Leistungsfähigkeit rekursiver Programme zu bestimmen, wofür wir in diesem Buch einige Beispiele sehen werden. Zum Beispiel tritt in Kapitel 9 die folgende Gleichung auf:

Formel

Der Wert von CN kann sehr leicht berechnet werden, wenn man wie im obenstehenden Programm ein Feld verwendet. In Kapitel 9 erörtern wir, wie diese Formel mathematisch behandelt werden kann; einige weitere rekurrente Beziehungen, die bei der Analyse von Algorithmen häufig auftreten, werden in Kapitel 6 betrachtet.

Demnach ist die Verwandtschaft zwischen rekursiven Programmen und rekursiv definierten Funktionen oft eher von philosophischer als von praktischer Art. Genau genommen hängen die oben aufgezeigten Probleme nicht mit dem Gedanken der Rekursion selbst zusammen, sondern mit ihrer Implementation: Ein (sehr leistungsstarker) Compiler könnte feststellen, daß die Funktion für die Fakultäten in Wirklichkeit mit einer Schleife implementiert werden kann und daß sich die Fibonacci-Funktion besser handhaben läßt, wenn man alle bereits berechneten Werte in einem Feld speichert. Später werden wir die Methoden zur Implementation rekursiver Programme ausführlicher betrachten.


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