Die Rekursion und Iteration sind zwei konkurrierende Art und Weisen der Wiederholung eines Vorgangs in der Programmierung.
Während die Iteration eine Menge an Vorgängen (typischerweise eingerückt in eine Schleife) wiederholt und ggf. die Anzahl der Wiederholungen zählt (For-Schleife), ist die Rekursion ein Funktionsaufruf der selben Funktion – d.h. eine Funktion ruft sich selbst auf.
I.d.R. wird Rekursion für Suchalgorithmen verwendet. Die rekursiv arbeitende Funktion wird dabei so oft von sich selbst aufgerufen, bis ein Suchmuster gefunden wurde oder die Suche aus anderen Gründen endet.
Genauso wie bei der Iteration, ist auch bei der Rekursion darauf zu achten, dass es eine Abbruchbedingung gibt – Sonst droht eine Endlosschleife.
Die Rekursion hat gegenüber der Iteration einige Nachteile. Die Rekursion ist langsamer, da bei jedem rekursiven Schritt eine Methode aufgerufen wird. Aus diesem Grund belegt die Rekursion außerdem mehr Speicherplatz.
Dennoch haben sich rekursive Methoden in bestimmten Bereichen durchgesetzt. Z.B. als eleganter Lösungsweg, um ein mathematisches Problem zu lösen. Auch bei der Suche in Binären Bäumen hat sich die Rekursion durchgesetzt, da über eine iterative Vorgehensweise sehr viele Schleifen notwendig wären.
Die Rekursion erleichtert die Nachvollziehbarkeit von komplexen Suchalgorithmen, für Neulinge ist die Rekursion jedoch anfangs nur schwer vorstellbar, jedoch auch nur eine Sache der Gewohnheit. Aber auch für geübte Programmierer, können besonders verschachtelte, rekursive Methoden schnell sehr verwirrend sein.
Beispiel einer rekursiven Suchmethode in C#
Ein Array mit einer Kapazität von 200 Feldern wird vollständig mit Zufallszahlen gefüllt.
[csharp] int[] liste;this.liste = new int[200];
Random random = new Random();
for (int i = 0; i < liste.Length; i++) { liste[i] = random.Next(0, 100); } [/csharp] Es soll eine Methode geschrieben werden, welche prüft, ob in das Array zufällig (mindestens) eine Zahl geschrieben wurde, welche inhaltlich mit dem Index übereinstimmt. Dies wäre beispielsweise der Fall, wenn das Array-Feld mit dem Index 17 auch den Inhalt "17" hat (this.liste[17] = 17).
Der klassische, nämlich iterative Weg (Iteration):
[csharp] private int IterationSearch(int startIndex){
for (int i = startIndex; i < this.liste.Length; i++) { if (this.liste[i] == i) { return i; } } return -1; } [/csharp] Die Methode benötigt als Parameter den Startwert des Arrays. Natürlich könnte auf den Startwert als Parameterübergabe verzichtet werden, da die Array-Indizierung grundsätzlich bei 0 anfängt. Über eine For-Schleife wird das Array durchsucht, mit jedem Schritt der For-Schleife wird ein Feld des Arrays auf Gleichheit von Inhalt und Index überprüft. Wird ein Feld gefunden, welches diese Bedingung erfüllt, wird die Methode verlassen und der Index zurückgegebenen. Durchläuft die Schleife das gesamte Array ohne ein solch gesuchtes Feld zu finden, beendet sich die Methode und gibt den Wert -1 zurück. (die -1 soll ein symbolischer Wert sein, welcher nichts weiter bedeutet als "das, was Du suchst, gibt es nicht". Der Wert -1 kann nicht mit einem Array-Index verwechselt werden und ist ein Klassiker aus der C-Programmierung)
Der rekursive Weg (Rekursion):
[csharp] private int RecursionSearch(int startIndex){
if (this.liste[startIndex] == startIndex)
{
return startIndex;
}
if (this.liste.Length > startIndex + 1)
{
return this.RecursionSearch(startIndex + 1);
}
return -1;
}
[/csharp]
Dieser Weg ist für Neulinge der rekursiven Programmierung sehr ungewöhnlich.
Die Methode bekommt bei jedem Aufruf einen Startwert als Parameter übergeben. Die Methode prüft als Erstes, ob der Inhalt des Feldes dem Index gleicht.
Ist dies der Fall, beendet sich die Methode sofort und liefert den entsprechenden Index zurück.
Ist dies jedoch nicht der Fall, wird geprüft, ob die Array-Indizierung bereits komplett durchlaufen wurde.
Wurde das Array bereits durchlaufen, beendet sich die Methode und gibt den Wert -1 zurück.
Verfügt das Array jedoch über einen weiteren Index, ruft die Methode sich selbst auf. Das Entscheidende ist hier der Parameter, dieser ist nämlich der Startwert um 1 erhöht.
An dieser Stelle wird klar, dass die rekursiv funktionierende Methode über einen Parameter verfügen muss. Die Zählung erfolgt über die Parameterübergabe.
Eine durch sich selbst aufgerufene Methode bekommt so einen neuen Startwert, dieser Startwert ist eine Zahl, welche nicht innerhalb der Methode inkrementiert wird, sondern nur bei der Parameterübergabe als Basis dient (Parameter: Basis + Zähleinheit).
Ein Rückgabewert, egal wie dieser auch aussehen mag, wird dann von der zu letzt aufgerufenen Methode nach oben hin bis zur zu erst aufgerufenen Methode zurückgereicht.