Als Neuling in der objektorientierten Programmierung suche ich eine Erklärung zur Funktionsweise der Rekursion. In meinem Viusal C# 2008 Buch finde ich leider nichts zu diesem Thema.

Oder sollten Methoden sich in C# aus irgendwelchen Gründen gar nicht selbst aufrufen ?

Für jeden Tipp dankbar,
el

Praktische Beispiele für Rekursionen sind schwirig zu erklären. Eine Rekursion ist, wenn sich eine Funktion immer wieder selbst aufruft. Theoretisch kann Sie das unendlich lange machen, wobei es keine sinn machen würde. Einen Sachverhalt den man typischerweise mit einer Rekusion erklären könnte wäre die Abstammung einer Person. "Otto ist das Kind von Frank und Steffi, Frank ist Kind von Olfa und Magith, Steffi ist Kind von Klaus und Berta, Olfa ist Kind von Heinz und Inge ..."
Jeweils immer X ist Kind von Y und Z wobei Y und Z ebenfalls wieder Kinder von Y1 und Z1 und Y2 und Z2 sind und so weiter.

Aus Performancesicht, ist es besser ohne Rekursionen zu arbeiten weil dan die Register nicht neu inizialisiert und geschrieben werden müssen. Aus programmiersicht sind rekursionen die elegantere Lösung weil leichter zu warten und übersichtlicher.

Auf http://de.wikipedia.org/wiki/Rekursion wird die Rekursion etwas ausführlicher erklärt und es werden auch, etwas weiter unten, Programmierbeispiel gezeigt. Sehr interessant ist das Programmierbeispiel 2, welche zeigt was eine Rekursion ist, und wie man sie auflößt (dh. das selbe Problem ohne Rekusion lößt).

Mit Rekursion:

//Quelle Wikipedia: http://de.wikipedia.org/wiki/Rekursion
// Absatz: "Programmierbeispiel II, Fakultätsberechnung"
fakultät_rekursiv(n)
{
  wenn n <= 1
      dann return 1
      sonst return ( n * fakultät_rekursiv(n-1) )
}

Das selbe Problem ohne Rekursion:

//Quelle Wikipedia: http://de.wikipedia.org/wiki/Rekursion Absatz:
// Absatz: "Programmierbeispiel II, Fakultätsberechnung"
fakultät_iterativ(n)
{
    fakultät = 1
    faktor = 2
    solange faktor <= n
    {
        fakultät = fakultät * faktor
        faktor = faktor + 1
    }
    return fakultät
}

Rekursion hat nichts mit einer Programmiersprache zu tun sondern ist ein Begriff der von der Mathematik geprägt ist. Einfach ausgedrückt wird dabei eine Folge (von Zahlen) derart definiert dass das nächste Glied aus dem vorigen berechnet wird. Somit wird immer weiter zurückgegangen bis ein Startpunkt erreicht ist. Dann werden die Schritte wieder vorwärts gelaufen und die nun bekannte Zwischenergebnisse verarbeitet.

Aufbauend auf dieser Definition wird das auch in der Programmierung angewandt. Es gibt Algorithmen die sich nicht iterativ - d.h. der Reihe nach jedes Element - lösen lassen und dann wird dies rekursiv gelöst. Es gibt auch Probleme dies sich rekursiv einfacher lösen lassen.

Das klassische Beispiel ist die Berechnung der Fakultät:

public int Fakultät(int n)
{
    if (n <= 1)
        return 1;

    return n * Fakultät(n - 1);
}

Was passiert:

• die Methode wird aufgerufen, zB mit 2
  
• die if-Bedinung ergibt false und somit wird dieselbe Methode wieder aufgerufen aber mit 1
  
• die if-Bedinung ergibt true und somit wird 1 zurückgegeben -> Startpunkt
  
• das Ergebnis dieses Rekursionschritts wird für das return von Schritt 2 verwendet und das Ergebnis berechnet. Da der Startpunkt erreicht wurde ist keine weitere Rekursion nötig.
  

Du kannst den Code kopieren und mit dem Debugger schauen was er macht.

Wie bereits erwähnt gibt es Algorithmen/Probleme die sich nicht/nur schwer iterativ lösen lassen. Dazu zählen zB

• Türme von Hanoi
  
• Determinatenberechnung mit dem Laplaceschen Entwicklungssatz
  
• Berechnung von Fibonacci-Zahlen
  
• anderes was auf Teile & Herrsche basiert
  

Es gibt also keinen Grund warum sich ein Methode nicht selbst aufrufen soll. Für den Prozessor gibt es keinen Unterschied ob er dieselbe oder eine andere Methode aufruft. Es ist nur darauf zu achten dass keine Endlosrekursion auftritt. Dies würde in einen 'Stack-Overflow' resultieren.

Bisher habe ich nur von der sogenannten 'direkten Rekursion' geschrieben. Es gibt auch die 'indirekte Rekursion'. D.h. Methode A ruft Methode B auf und diese wiederum Methode A solange bis ein Startpunkt erreicht ist. Vom Prinzip her ändert sich nichts.

Es gibt Probleme, die sich rekursiv "schöner" lösen lassen, als iterativ. Wie schon erwähnt bedeutet Rekursion, dass sich eine Funktion bis zu einer Abbruch-Bedingung selbst wieder aufruft, meist mit Parametern, die sich aus dem vorherigen Aufruf ergeben.

Das Problem mit Rekursion ist, dass man oft relativ lange braucht, um auf einen geeigneten Algorithmus zu kommen, der dann oft aber sehr elegant ist.

Ein Beispiel aus der Mathematik wurde schon gegeben: die Fakultät. Ein weiteres wären die Fibonacchi Zahlen. Eine Fibonacchi-Zahl ist definiert als die Summe der beiden vorangegangenen Fibonacchi-Zahlen. Aus dem Kopf müsste das so aussehen:

public int Fib(int i)
{
    if (i < 0) throw new ArgumentException("Fib ist für negative Zahlen nicht definiert!");
    if (i == 0 || i == 1) return 1;
    return Fib(i-1) + Fib(i-2);
}

Ein Problem aus der Informatik wäre z.B. das Hinzufügen aller Ordner der Festplatte zu einem Baum-Control. Hier kann man einen rekursiven Algorithmus entwerfen, der in folgenden Schritten arbeitet:

• Erstelle eine interne Liste aller Unterordner in einem gegebenen Ordner
  
• Für jeden dieser Unterordner: Füge einen Knoten in den Baum ein und rufe rekursiv für diesen Ordner auf
  
• Wenn es keine Unterordner mehr gibt, höre auf
  

In Pseudocode sähe das etwa so aus:

funktion Unterordner(string root, TreeNode rootNode)
{
    List<string> unterordner = HoleUnterordner(root);
    foreach (string o in unterordner)
    {
       neuerKnoten = ErzeugeNodeIn(rootNode, o);
       Unterordner(o, neuerKnoten);
    }
}

Auf die Frage hin wie sich das Beispiel der Unterordner auch ohne Rekursion (also iterativ) lösen läßt, hier mal der entsprechende Quellcode:

DirectoryInfo basedir = new DirectoryInfo("C:");
Queue<DirectoryInfo> qListSubFolders = new Queue<DirectoryInfo>();

qListSubFolders.Enqueue(basedir);

while (qListSubFolders.Count>0) {
    DirectoryInfo subFolderDir = qListSubFolders.Dequeue();
    Console.WriteLine(subFolderDir.FullName);

    if(subFolderDir.GetDirectories().Length > 0)
        foreach (DirectoryInfo sF in subFolderDir.GetDirectories())
            qListSubFolders.Enqueue(sF);
}