Rekursive Programmierung

Rekursive Programmierung

Rekursive Programmierung ist ein Programiermethode, die darauf beruht, dass es in einem Computerprogramm eine Funktion oder Methode gibt, die sich selbst immer wieder aufruft. Wichtig dabei ist eine Abbruchbedingung in dieser Funktion, weil sich das rekursive Programm sonst (theoretisch) bis in alle Ewigkeit selbst aufrufen würde. Die rekursive Programmierung findet oft Anwendung in prozeduralen und objektorientierten Programmiersprachen.

Ein Beispiel für die Verwendung einer rekursiven Programmierung ist das berechnen der Fakultät einer Zahl. Das funktioniert beispielsweise wie folgt:

Es existiert eine Funktion fac, die eine Zahl x als Eingabewert bekommt. Diese Funktion multipliziert x mit dem Rückgabewert von fac(x-1) außer x=0, dann liefert die Funktion das Ergebnis 1 (Abbruchbedingung).

Beispiel in Pascal:

function fac (x : Integer): x;
begin
  if x = 0 then fac := 1
           else fac := x * fac(x - 1);
end;

Mit der Startzahl x=4 würde der Computer rechnen:

fac(4*fac(3*fac(2*fac(1))))

heraus käme dann nach Adam Riese 24

Rekursive Programme haben keine gute Performance. Durch die wiederholten Funktionsaufrufe wird immer wieder derselbe Methodeneintrittscode bearbeitet und jedesmal der Kontext gesichert, was zu hohem Arbeitsspeicherverbrauch führt. Die meisten rekursiven Algorithmen lassen sich jedoch durch iterative Programmierung implementieren.

Nicht alle höheren Programmiersprachen lassen rekursive Aufrufe zu; ein Beispiel dazu ist Fortran.