Werner-von-Siemens-Gymnasium: Fächer - Informatik - Materialien

Informatik

Rekursion

Unterprogramm Mops;
Ausgabe('Ein Mops kam in die Küche ');
Ausgabe('und stahl dem Koch ein Ei. ');
Ausgabe('Da nahm der Koch den Löffel ');
Ausgabe('und schlug den Mops zu Brei. ');
Ausgabe('Da kamen viele Möpse ');
Ausgabe('und gruben ihm ein Grab ');
Ausgabe('und setzten einen Grabstein, ');
Ausgabe('auf dem geschrieben stand: ');
Mops;
Ende des Unterprogramms Mops

Ein Verfahren wird rekursiv genannt, wenn es sich im Lauf der Abarbeitung selbst aufruft.
Damit das Verfahren endet/terminiert und sich nicht ständig erneut aufruft, muss eine Abbruchbedingung enthalten sein.

Im Prinzip läuft jede Rekursion nach folgendem Muster ab:

Verfahren Rekursion

      ist die Abbruchbedingung erreicht,
      dann Abbruchanweisung(en)
      sonst Anweisung(en) mit Aufruf(en) des Unterprogramms "Rekursion"

Ende des Verfahrens Rekursion

Die Variable(n), die in der Abbruchbedingung abgeprüft werden, müssen sich ändern, damit die Bedingung erfüllt werden kann.

Ausnahmsweise hier einmal ein mathematisches Beispiel - die Berechnung der Fakultät einer ganzen, positiven Zahl:

n! = 1*2*3*4*5* ... (n-1)*n

oder für uns hier besser definiert:

n! =

1, falls n = 0 oder 1

n * (n-1)!, falls n > 1

Ein entsprechendes Unterprogramm könnte folgendermaßen aufgebaut sein:

Funktion Fakultaet (Eingabeparameter n - positive, ganze Zahl) liefert eine positive, ganze Zahl

      Ist n <= 1
      dann ist das Ergebnis des Unterprogramms 1
      sonst ist das Ergebnis des Unterprogramms n*Fakultaet(n-1)

Ende des Unterprogramms Fakultaet

Ruft man nun zum Beispiel Fakultaet(4) auf, läuft folgendes ab:

Fakultät(4)

An diesem Beispiel erkennt man einen Nachteil der Rekursion: von jedem Unterprogramm, das einen erneuten Rekursionsaufruf startet, werden die laufenden Variablenbelegungen und die Einsprungstelle nach Beendigung des Aufrufs aufgehoben. Dieser Speicherbereich (stack = Stapel) kann bei großer Rekursionstiefe schnell anwachsen und den verfügbaren Speicher ausfüllen, was einen Programmabruch zur Folge hat.
Obwohl rekursive Verfahren oft kurz zu notieren und elegant sind, einige Algorithmen nicht oder nur sehr umständlich iterativ zu formulieren sind, sei auch noch ein zweites Problem genannt - einige sind nur schwer durchschaubar.

verantw.: J. Frank