Programmiersprache C/C++

3.4.5. Rekursion

Rekursion bezeichnet die Definition von "etwas" durch sich selbst.
Rekursive Algorithmen nehmen auf sich selbst Bezug.

Bekannte Beispiele für die Anwendung der Rekursion sind zum Beispiel 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 die Rekursion 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 einer Reihe von Situationen alternativ zur Iteration eingesetzt werden.
Mit Hilfe der Rekursion läßt sich eine Anzahll 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 Speicherverwaltung (Stack) beträchtlich erhöhen kann.

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

Beispiel 1:

  #include <stdio.h>

  int fakultaet(int n)
  {
    if ( n == 1 )
      return  1;
    else
      return  n * fakultaet(n-1);
  }

  int main(void)
  {
    int m, n;

    for ( n=1; n<=17; n++ )
      printf("n = %2d  n! = %10d\n", n, fakultaet(n));
  }

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 int.
- Typischerweise wird bei der INTEGER-Arithmetik das Verlassen des Wertebereiches nicht als Fehler signalisiert.
- Der Wertebereich von int ist unterschiedlich bei verschiedenen C-Systemen. Dies bewirkt unterschiedliches Laufzeitverhalten !
  Besser wäre in diesem Fall die Verwendung von long bzw. unsigned long. /UL>

Protokoll der Ausführung des obigen Programms nach Übersetzung mit einem 32-Bit-System 16-Bit-System 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: int fakultaet(int n) { int i, fak = 1; for ( i=2; i<=n; i++ ) fak *= i; return fak; } Zurück zum Menü Zurück zur vorigen Seite Weiter zur nächsten Seite P. Böhme, 04.02.1996