Datenstruktur - Grundlagen der Rekursion

In einigen Computerprogrammiersprachen kann sich ein Modul oder eine Funktion selbst aufrufen. Diese Technik wird als Rekursion bezeichnet. In der Rekursion eine Funktionα ruft sich entweder direkt auf oder ruft eine Funktion auf β das wiederum ruft die ursprüngliche Funktion auf α. Die Funktionα heißt rekursive Funktion.

Example - eine Funktion, die sich selbst aufruft.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - eine Funktion, die eine andere Funktion aufruft, die sie wiederum erneut aufruft.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Eigenschaften

Eine rekursive Funktion kann wie eine Schleife unendlich werden. Um eine unendliche Ausführung der rekursiven Funktion zu vermeiden, muss eine rekursive Funktion zwei Eigenschaften haben:

Base criteria - Es muss mindestens ein Basiskriterium oder eine Grundbedingung vorhanden sein, sodass sich die Funktion bei Erfüllung dieser Bedingung nicht mehr rekursiv aufruft.
Progressive approach - Die rekursiven Aufrufe sollten so fortschreiten, dass sie bei jedem rekursiven Aufruf den Basiskriterien näher kommen.

Implementierung

Viele Programmiersprachen implementieren die Rekursion mittels stacks. Im Allgemeinen, wann immer eine Funktion (caller) ruft eine andere Funktion auf (callee) oder selbst als Angerufene überträgt die Aufruferfunktion die Ausführungskontrolle an den Angerufenen. Dieser Übertragungsprozess kann auch einige Daten beinhalten, die vom Anrufer an den Angerufenen weitergeleitet werden müssen.

Dies bedeutet, dass die Aufruferfunktion ihre Ausführung vorübergehend unterbrechen und später fortsetzen muss, wenn die Ausführungssteuerung von der Angerufenenfunktion zurückkehrt. Hier muss die Aufruferfunktion genau an dem Punkt der Ausführung beginnen, an dem sie sich selbst in die Warteschleife stellt. Es benötigt auch genau die gleichen Datenwerte, an denen es gearbeitet hat. Zu diesem Zweck wird ein Aktivierungsdatensatz (oder Stapelrahmen) für die Aufruferfunktion erstellt.

Dieser Aktivierungsdatensatz enthält die Informationen zu lokalen Variablen, formalen Parametern, der Rücksprungadresse und allen Informationen, die an die Aufruferfunktion übergeben werden.

Analyse der Rekursion

Man kann argumentieren, warum Rekursion verwendet werden soll, da dieselbe Aufgabe mit Iteration ausgeführt werden kann. Der erste Grund ist, dass die Rekursion ein Programm lesbarer macht und aufgrund der neuesten erweiterten CPU-Systeme die Rekursion effizienter ist als Iterationen.

Zeitliche Komplexität

Bei Iterationen nehmen wir die Anzahl der Iterationen, um die zeitliche Komplexität zu zählen. Ebenso versuchen wir im Falle einer Rekursion unter der Annahme, dass alles konstant ist, herauszufinden, wie oft ein rekursiver Aufruf erfolgt. Ein Aufruf einer Funktion ist Ο (1), daher ergibt die (n) Häufigkeit, mit der ein rekursiver Aufruf erfolgt, die rekursive Funktion Ο (n).

Raumkomplexität

Die Speicherplatzkomplexität wird als die Menge an zusätzlichem Speicherplatz gezählt, die für die Ausführung eines Moduls erforderlich ist. Bei Iterationen benötigt der Compiler kaum zusätzlichen Speicherplatz. Der Compiler aktualisiert ständig die Werte der in den Iterationen verwendeten Variablen. Im Falle einer Rekursion muss das System jedoch bei jedem rekursiven Aufruf einen Aktivierungsdatensatz speichern. Daher wird angenommen, dass die Raumkomplexität der rekursiven Funktion höher sein kann als die einer Funktion mit Iteration.