Rekursionen: Genial und trotzdem fatal

Häufig finden Rekursionen in Bereich mathematischer Beschreibungen oder in der Programmierung Anwendung. Dabei beschreibt eine rekursive Funktion den Aufruf von sich selbst während der Programmlaufzeit.

Oder in anderen Worten: Eine Funktion ruft sich bei der Ausführung selbst auf.

Ein gängiges Beispiel ist die Berechnung von Fakultäten, bei dem die Zahl jeweils mit allen ganzzahligen Vorgängern multipliziert wird, somit ist die Fakultät von 3 gleich 3 2 1 also 6. Ein funktionaler Code mit rekursiver Eigenschaft sieht in etwa wie folgt aus:

function Faculty ( number ) {

  if ( number == 1 ) {  // Abbruchkriterium

    return 1;

  }else{

    return number * Faculty ( number - 1 );
  }
}

Das Abbruchkriterium, um eine endlose Ausführung der Funktion selbst zu vermeiden ist dabei der obere Teil:

if( number == 1 ) {

  return 1;
}

Nimmt man als Parameter den Wert 5, würde während der Ausführung von Faculty(5) folgende Struktur entstehen:

>Faculty(5)
->Faculty(4)
 ->Faculty(3)
  ->Faculty(2)
   ->Faculty(1) // Abbruchkriterium

=> Ergebnis: 120

Man erkennt, dass die Funktion somit fünf mal aufgerufen wird, bis letzten Endes das Abbruchkriterium erreicht wird und das Ergebnis ausgegeben wird. Der iterative Zwilling hingegen würde in etwa wie folgt aussehen:

function Faculty ( number ) {

  fac = number;

  for ( i = number - 1; i > 1; i--) {

    fac *= i;
  }

  return fac;
}

Was ist nun der Unterschied?

Der Speicherverbrauch!

Bei jedem Funktionsaufruf wird "Overhead" erzeugt, darunter fallen unter anderem die Reservierung von Speicherplatz für jeden einzelnen Funktionsaufruf. Bei der iterativen Variante fällt dieser "Overhead" nur einmal an und zwar für den erstmaligen Funktionsaufruf. Eine Schleife benötigt natürlich ebenfalls einen gewissen Speicher während der Ausführung, allerdings liegt dieser deutlich niedriger im Vergleich zu einer rekursiven Verarbeitung mit Funktionsaufruf.

Performance-technisch betrachtet liegen beide Varianten sehr nahe bei einander. (Abhängig vom Computer auf dem der Test ausgeführt wird und welche Programmiersprache verwendet wird.) In weiteren Durchläufen konnten zudem keine größeren zeitlichen Abweichungen festgestellt werden. Lediglich bei dem Test zur Berechnung von Fakultäten mittels rekursiven Funktionsaufruf konnte ein erhöhter Speicherbedarf bei großen zahlen festgemacht werden.

Sollten Rekursionen grundsätzlich vermieden werden?

Naja, es kommt darauf an! Für manche Situationen machen Rekursionen mehr Sinn.

Zum Beispiel beim Durchlaufen von Bäumen oder Dateipfaden oder allgemein gesprochen in Fällen, bei denen man die exakte Anzahl der Durchläufe vorher nicht genau bestimmen kann oder unbekannt ist. Bei dem Beispiel zur Berechnung von Fakultäten wäre eine iterative Variante vorzuziehen, da hier eine Rekursion keine erheblichen Vorteile bringt. Für manche Entwickler mag es vielleicht die leichtere Variante sein, dafür wird eindeutig mehr Overhead/Speicher benötigt, welcher vermeidbar ist und vermieden werden sollte. Durch den Verzicht von Rekursionen bei der Berechnung von Fakultäten ergibt sich somit ein positives Bild in Bezug auf nachhaltiger Programmierung.

5 Beispiele für nachhaltige Programmierung