Erklärungen zur Rekursion


Man muß unterscheiden zwischen "rekursiven Prozeduren" und "rekursiven
Prozessen".

Rekursive Prozeduren sind Teile eines Programms, geschrieben in einer
bestimmten Programmiersprache, die sich selbst direkt oder indirekt
aufrufen. Die Betrachtung erfolgt dabei statisch (zur Compile-Zeit).

(Abstrakte) rekursive Prozesse sind die durch ein Programm bzw. einen
Programmteil beschriebenen Operationen auf einer abstrakten Maschine (ohne
Beschränkung durch Speicherplatz oder Zeit). Die Betrachtung erfolgt dabei
zur Laufzeit.  Welcher Prozeß sich aus einer Prozedur ergibt, hängt
eventuell vom Compiler bzw. Interpreter ab.

Bei rekursiven Prozeduren kann man unterscheiden zwischen

 * direkter und indirekter Rekursion

   Bei "direkter Rekursion" ruft eine Prozedur sich selbst auf und wird nur
   durch sich selbst aufgerufen.

   Bei "indirekter Rekursion" ruft eine Prozedur a eine Prozedur b auf, die
   wiederum (eventuell indirekt) Prozedur a aufruft.

 * linearer, nicht-linearer und geschachtelter Rekursion

   Bei "linearer Rekursion" ruft die Prozedur bei jedem denkbaren Durchlauf
   (Abarbeitungsweg) maximal eine linear rekursive Prozedur auf (und keine
   nicht linear rekursiven Prozeduren).
   Hinweis: Es können durchaus mehrere rekursive Aufrufe vorhanden sein,
   wenn diese in unterschielichen Zweigen einer Fallunterscheidung stehen.

   Bei "nicht-linearer Rekursion" (auch "Baumrekursion" oder "kaskadenartige
   Rekursion" genannt) gibt es in einem denkbaren Durchlauf mehrere Aufrufe
   einer oder mehrerer rekursiver Prozeduren. Wenn dabei ein rekursiver
   Aufruf das Argument eines anderen rekursiven Aufrufs ist, spricht man von
   "geschachtelter Rekursion".

 * Endaufruf und Endrekursion

   Als "Endaufruf" wird ein Prozeduraufruf bezeichnet, bei dem eine Prozedur
   das Ergebnis einer anderen Prozedur ohne weitere Verarbeitung
   zurückliefert, die aufgerufene Prozedur also die letzte Anweisung der
   aufrufenden Prozedur darstellt. Eine linear rekursive Prozedur, bei der
   alle rekursiven Aufrufe Endaufrufe sind, wird als "endrekursive Prozedur"
   (tail recursive procedure) bezeichnet.

Diese Begriffe übertragen sich auf Prozesse, indem der konkrete Abauf
betrachtet wird. Dabei ist es nicht immer einfach, anhand der Prozedur zu
entscheiden, was für eine Art von Prozeß erzeugt wird. Beispiel:

  (define (dec x)
    (- x 1))

  (define (g x)
    (cond ((zero? x) 1)
          ((test? x) (h x x))
          (else (g (dec x))) ))

  (define (h u v)
    (+ (g (dec u)) (g (dec v))) )

Wenn die Prozedur test? immer den Wert #f liefert, handelt es sich beim
Prozeß der Prozedur g um einen (linearen) endrekursiven Prozeß. Wenn test?
mindestens einmal den Wert #t liefert, handelt es sich um einen indirekten
nicht-linear rekursiven Prozeß.

Nicht jedem endrekursiven Prozeß liegt also eine endrekursiven Prozedur
zugrunde. Andererseits führt aber jede endrekursive Prozedur zu einem
endrekursiven Prozeß.

Zusätzlich gibt es noch

 * iterative Prozeduren (oder Programmabschnitte)

   Bei diesen wird ihr Zustand durch eine feste, von der Eingabe unabhängige
   Anzahl von Zustandsvariablen beschrieben (konstanter Platzbedarf). Die
   Schleifenkonstrukte (z.B. "do" in Scheme oder "while" in Java) erzeugen
   solche Programmabschnitte.

Entsprechend gibt es auch iterative Prozesse. Scheme realisiert Endaufrufe
grundsätzlich durch eine iterative Abarbeitung (technisch gesprochen: die
Ausführung der aufgerufenen Prozedur wird durch einen Sprung fortgesetzt,
ohne daß dabei auf dem Stack ein neuer Frame erzeugt wird), wodurch
endrekursive Prozeduren als iterative Prozesse besonders effizient
abgearbeitet werden.

Achtung: Daß ein Prozeß linear rekursiv ist, bedeutet nicht, daß seine
Zeitkomplexität linear ist (auch wenn dies häufig der Fall sein wird). Es
ist noch nicht einmal sicher gestellt, daß der Prozeß überhaupt terminiert.

Es gilt jedoch: Die Speicher-Komplexität linear rekursiver, nicht iterativer
Prozesse ist linear.


(Dietmar Lippold, dietmar.lippold@informatik.uni-stuttgart.de, 07.11.02,
 letzte Änderung 06.11.03)