Programmiersprache Pascal

Rekursion

Rekursion bezeichnet die Definition von "etwas" durch sich selbst.
In Programmiersprachen spielt die Rekursion eine Rolle in Gestalt von

rekursiven Algorithmen,
rekursiven Datentypen.

Rekursive Algorithmen sind ersetzbar durch iterativ arbeitende Algorithmen.

Bekannte Beispiele für die Anwendung der Rekursion sind z.B. die Berechnung

der Fakultätsfunktion n!

   n! = n * (n-1)!    für n >= 2
   n! = 1             für n = 1

der Fibonacci-Zahlen f(n)

   f(n) = f(n-2) + f(n-1)      n >= 3
   f(n) = 1                    n = 1, 2

Für rekursive Algorithmen sind wichtig:

die Rekursionsverankerung und
die eigentliche Rekursionsvorschrift

Die Rekursionsvorschrift nimmt auf sich selbst Bezug. Die Rekursionsverankerung sorgt dafür, daß die Rekursion nach endlich vielen Schritten endet.

Zu beachten sind die Situationen, in denen die Rekursionsvorschrift nicht gilt.
In den obigen Beispielen ist dies für negatives n der Fall. Ein Eintritt in die Rekursionsvorschrift mit negativem n führt dazu, daß die Rekursionsverankerung nicht greift, d.h. die Rekursion endet nicht nach endlich vielen Schritten.

Rekursion kann in bestimmten Situationen alternativ zur Iteration eingesetzt werden.
Mit Hilfe der Rekursion läßt sich eine Reihe von Algorithmen elegant und kurz darstellen.
Für die rechentechnische Umsetzung sind rekursive Algorithmen jedoch nicht in jedem Fall die effektivste Lösung, da sich bei hoher Rekursionstiefe der Aufwand für die dynamische Speicherverwaltung beträchtlich erhöhen kann.

Rekursives Arbeiten wird nicht durch alle Programmiersprach(version)en unterstützt, ist jedoch fester Bestandteil von Pascal.

Beispiel 1:

  PROGRAM rekurs(OUTPUT);

  FUNCTION fakultaet(n: INTEGER) : INTEGER;
  BEGIN
    IF n = 1 THEN
      fakultaet := 1
    ELSE
      fakultaet := n * fakultaet(n-1);
  END;

  VAR m, n : INTEGER;

  BEGIN
    FOR n:=1 TO 17 DO BEGIN
      m := fakultaet(n);
      Writeln('n = ', n:2, '  n! = ', m:10);
    END;
  END.

Bemerkungen:

Der Aufruf fakultaet(n) mit n <= 0 führt zu einer unendlichen Schleife.
Bereits für relativ kleine n verläßt der Wert von n! den Wertebereich des Datentyps INTEGER.
- Typischerweise wird bei der INTEGER-Arithmetik das Verlassen des Wertebereiches nicht als Fehler signalisiert.
- Der INTEGER-Wertebereich ist unterschiedlich bei verschiedenen Pascal-Systemen. Dies bewirkt unterschiedliches Laufzeitverhalten !

Protokoll der Ausführung des obigen Programms unter

          Pascal++               Turbo Pascal
  n =  1  n! =          1        n =  1  n! =          1
  n =  2  n! =          2        n =  2  n! =          2
  n =  3  n! =          6        n =  3  n! =          6
  n =  4  n! =         24        n =  4  n! =         24
  n =  5  n! =        120        n =  5  n! =        120
  n =  6  n! =        720        n =  6  n! =        720
  n =  7  n! =       5040        n =  7  n! =       5040
  n =  8  n! =      40320        n =  8  n! =     -25216
  n =  9  n! =     362880        n =  9  n! =     -30336
  n = 10  n! =    3628800        n = 10  n! =      24320
  n = 11  n! =   39916800        n = 11  n! =       5376
  n = 12  n! =  479001600        n = 12  n! =      -1024
  n = 13  n! = 1932053504        n = 13  n! =     -13312
  n = 14  n! = 1278945280        n = 14  n! =      10240
  n = 15  n! = 2004310016        n = 15  n! =      22528
  n = 16  n! = 2004189184        n = 16  n! =     -32768
  n = 17  n! = -288522240        n = 17  n! =     -32768

Alternative Realisierung der Fakultätsfunktion durch Iteration:

  FUNCTION fakultaet(n: INTEGER) : INTEGER;
  VAR i, f : INTEGER;
  BEGIN
    f := 1;
    FOR i:=2 TO n DO
      f := i*f;
    fakultaet := f;
  END;

P. Böhme, 06.09.1996