7.8    Rekursionen

Man spricht von Rekursion, wenn eine Funktion sich selbst aufruft, noch bevor sie ordnungsgemäß beendet wurde. Damit sich aber eine solche rekursive Funktion nicht unendlich oft selbst aufruft, sondern irgendwann auch zu einem Ergebnis kommt, benötigen Sie eine Abbruchbedingung. Sonst kann es passieren, dass Ihr Computer abstürzt, da eine Funktion, die sich immer wieder selbst aufruft, jedes Mal eine Rücksprungadresse, den Wert der Variablen und – falls noch nicht freigegeben – den Rückgabewert auf dem Stack speichert. Der dafür zur Verfügung stehende Speicher wird irgendwann voll sein beziehungsweise überlaufen. Dieser Zustand wird Stapelüberlauf oder Stack Overflow genannt. Wie der Computer damit umgeht, hängt vom Betriebssystem ab. Der harmloseste Fall ist noch, dass sich Ihr Programm mit der entsprechenden Meldung beendet.

Es folgt nun ein einfaches Beispiel, womit die Fakultät der Zahl n berechnet wird. Die Fakultät der Zahl 5 ist z. B. 1*2*3*4*5=120.

00  // Kapitel7/fakultaet.c
01  #include <stdio.h>

02  long fakul( long n ) {
03    if(n != 0 ) {
04      return n * (fakul(n-1));
05    }
06    return 1;
07  }

08  int main(void) {
09    printf("Fakultaet von 6: %ld\n", fakul(6));
10    printf("Fakultaet von 8: %ld\n", fakul(8));
11    return 0;
12  }

Listing 7.8    fakultaet.c berechnet die Fakultät einer Zahl durch eine Rekursion.

Zunächst wird die Funktion fakul() aus der main()-Funktion zweimal aufgerufen. Einmal mit der Zahl 6 (Zeile (09)) und einmal mit der Zahl 8 (Zeile (10)). Innerhalb der Funktion fakul() wird zunächst überprüft (Zeile (03)), ob der Wert von n ungleich 0 ist. Diese Überprüfung ist auch gleichzeitig die Abbruchbedingung für die Rekursion, weil eine wiederholte Multiplikation mit 0 (n*0) stets das Ergebnis 0 ergeben würde. In Zeile (04) wird der aktuelle n-Wert mit dem Rückgabewert eines erneuten rekursiven Funktionsaufrufs von fakul() multipliziert. Als Argument wird n nun um eins reduziert. Bei einer Fakultät von 6 wäre das Ergebnis somit 6*5*4*3*2*1. Bei einem erneuten rekursiven Aufruf mit fakul(0) greift dann die Abbruchbedingung der Zeile (03), dass n!=0 nicht mehr zutrifft. Es wird dann mit return der Wert 1 (Zeile (06)) zurückgegeben. Auf dem Stack liegen nun unter Umständen mehrere Funktionsaufrufe, die dann von unten nach oben bis zur main()-Funktion abgearbeitet werden, inklusive dem korrekten Rücksprung in die Hauptfunktion.

Das Programm gibt nun für die Zahlen 6 und 8 Folgendes aus:

Fakultät von 6: 720
Fakultät von 8: 40320

An dieser Stelle sei gesagt, dass dieses Beispiel auch ohne Rekursion programmiert werden kann, aber dies soll Teil einer Übungsaufgabe am Ende des Kapitels sein. Des Weiteren muss erwähnt werden, dass sich fast alle mathematischen Verfahren (auch Algorithmen genannt) auch ohne Rekursionen programmieren lassen. Es gibt allerdings viele Algorithmen, die sich wesentlich einfacher mit Rekursionen formulieren und programmieren lassen als ohne. Meistens werden z. B. rekursive Funktionen beim Durchlaufen von baumartigen Strukturen (Stichwort: binäre Bäume, binäre Suche usw.) verwendet, obgleich es auch dafür häufig eine iterative Lösung gibt. Ein anderes Beispiel ist das Backtracking, mit dem man z. B. Wege durch Irrgärten finden kann. Ohne Rekursion ist dieses Problem kaum bzw. nur sehr schwer lösbar, mit Rekursion in ein paar Zeilen. Schon die Monster im Pacman-Spiel verwenden Backtracking, und bekanntlich läuft dieses Spiel auch auf den ältesten Computern.