Rekursion

Kann mir bitte jemand die Rekursion erklären?
Ich verstehe das nicht.

*darauf wettet, dass sich mindestens 1 User vordrängelt, während ich den Post schreibe*^^

Rekursion ist der Fachbegriff für "Wiederaufruf" eines Programms. Dabei ruft sich ein Programm solange selbst auf, bis irgendwas geschieht, dass das Programm nicht mehr aufruft ;) .

Ein kleines Beispiel, wie Rekursion in QBasic aussehen würde:

Code:

---

:Label
Variable% = Variable% + 1
IF Variable% < 13 THEN
    GOTO Label
ELSE
    irgendwas...
END IF

---

Damit kann man u. a. auch komplexe Schachprogramme schreiben. Dadurch rechnet z. B. der Computer solange alle möglichen Züge des Brettes durch, bis es den besten Weg gefunden hat.

Hoffe, ich konnte helfen.

EDIT: Wow, ich bin der erste^^.

Rekursion erklaert man am besten an einem Beispiel ...

Dazu waehle ich mir, das Zaehlen von Knoten in einem Binaerbaum ..

Ein Knoten in einem Baum hatt immer zwei verweise auf andere knoten, die als gesamtheit dann den baum ergeben. Ist der Verweis 0, so geht dort der Baum nicht weiter ...

In Pseudocode sieht das dann so aus ...

Code:

---

struct knoten
{ knoten* links;
  knoten* rechts;
}

---

nun schreiben wir die funktion, die alle knoten im Baum zaehlen soll ...

wir uebergeben ihr den startknoten des Baumes und die Variable, in der wir die Anzahl speichern wollen. Ist der uebergebene Knoten nicht 0, so erhoehen wir die Variable um 1. Danach ruft sich unsere Funktion abermals mit dem rechten und dem linken knoten auf.

Code:

---

void zaehle(knoten* node, int &anzahl)
{ if (node!=0)
  { anzahl++;
    zaehle(node->links, anzahl);
    zaehle(node->rechts, anzahl);
  }
}

---

Wir stellen uns nun einen Beispielbaum vor, der folgende struktur hat ... A.rechts=B, A.links=F, B.rechts=D, B.links=C, C.rechts=E. Alles, wo keine Verzweigung hinfuehrt, sei mit 0 besetzt.

Code:

---

          A
        / \
        F  B
          / \
          C  D
          \
            E

---

Wenden wir nun unsere Funktion Zaehle auf A an

Code:

---

int anzahl=0;
zaehle(A,anzahl);

---

node ist in diesem Fall A, Anzahl ist 0
Da node != 0 ist, wird Anzahl um 1 erhoeht.
Nun ruft zaehle sich selbst auf mit node.links und anzahl, also im Klartext als zaehle(F,1)

node ist nun F, Anzahl ist 0
Da node != 0 ist, wird Anzahl um 1 erhoeht.
Nun ruft zaehle sich selbst auf mit node.links und anzahl.
Da F keine weiteren verzweigungen hat, ind sowohl F.links als auch F.rechts 0

fuer f.links folgt zaehle(0,2)

Da die if bedingung in zaehle nicht erfuellt ist, passiert gar nichts, und die funktion kehrt unveraendert zur aufrufenden funktion zurueck.

als naechstes folgt nun der aufruf
fuer f.rechts als zaehle(0,2)

auch hierbei passiert gar nichts.
Somit ist auch die funktion zaehle(f,1) abgearbeitet, und kehrt somit zur aufrufenden funktion zurueck, um den A.rechts teil zu bearbeiten

zaehle(B,2)

B ist ungleich 0 und somit steigt anzahl um 1
nun folgt der aufruf von B.links als
zaehle(C,3)

C ist ungleich 0 und somit steigt anzahl wieder. Da C keine Verzweigung nach links hat, erfolgt der Aufruf Zaehle(0,4), der keine auswirkung hat, und der Aufruf von C.rechts als zaehle(E,4).

Da E weder linken noch rechten nachbarn hat, selber aber ungleich 0 ist, wird nur anzahl um 1 erhoeht, und zweimal zaehle(0,5) eufgerufen, was ja nichts veraendert

Nun ist der E zweig abgearbeitet, und es geht zurueck zum C Zweig. Da hier jetzt aber der rechte zweig auch abgearbeitet ist, ist die Funktion Zaehle(C,..) auch abgearbeitet, und es geht zurueck zur B Instanz. Der Aufruf von zaehle(B.links, ..) ist jetzt abgearbeitet, nun folgt der Aufruf von zaehle(B.rechts, 5) was mit zaehle(D,5) gleichzusetzen ist ...

Anzahl wird abermals um 1 erhoeht, da D ungleich 0 ist.
D.rechts und D.links sind aber 0, wodurch die Aufrufe von zaehle(D.links,6) und zaehle(D.rechts,6) keine wirkung haben.
Somit ist der D Zweig abgearbeitet, und es geht zurueck zu B.
Auch in B ist nun der linke und der rechte zweig abgearbeitet, wodurch die Funktion zaehle(B,..) beendet ist, und zur aufrufenden funktion zaehle(A,..) zurueckgekehrt wird

Da auch in A alles abgearbeitet ist, wird auch zaehle(A,..) beendet, und zum aufrufenden programm zurueck gegeben. In der Variablen anzahl steht nun die richtige Anzahl an Knoten des Baumes, naemlich 6

Nochmal zum zusammenfassen, welche Funktionen nacheinander aufgerufen werden ...

Zaehle(A,0) aus dem Hauptprogramm
Zaehle(F,1) aus zaehle(A,..) als zaehle(A.links,..)
Zaehle(0,2) aus zaehle(F,..) als zaehle(F.links,..)
Zahele(0,2) aus zaehle(F,..) als zaehle(F.rechts,..)
Zaehle(B,2) aus zaehle(A,..) als zaehle(A.rechts,..)
Zaehle(C,3) aus zaehle(B,..) als zaehle(B.links,..)
Zaehle(0,4) aus zaehle(C,..) als zaehle(C.links,..)
Zaehle(E,4) aus zaehle(C,..) als zaehle(C.rechts,..)
Zaehle(0,5) aus zaehle(E,..) als zaehle(E.links,..)
Zaehle(0,5) aus zaehle(E,..) als zaehle(E.rechts,..)
Zaehle(D,5) aus zaehle(C,..) als zaehle(C.rechts,..)
Zaehle(0,6) aus zaehle(D,..) als zaehle(D.links,..)
Zaehle(D,6) aus zaehle(D,..) als zaehle(D.rechts,..)

nochmal zur Erinnerung: diese ganze rekursive Funktionskaskade wurde durch den einzeiligen Funktionsaufruf

zaehle(A,anzahl) ausgeloest

Somit sieht man, dass Rekursion ein sehr maechtiges, aber doch recht komplexes werkzeug sein kann, vor allem, wenn es um stetig wiederkehrende, aber leicht modifizierte aufgaben geht. Besonders geeignet ist Rekursion fuer Baumstrukturen jeder Art, so z.B. auch Dateisuche in Unterverzeichnissen ...

Hoffe, das beispiel war einigermassen lehrreich ...

Gruss Ineluki

Danke für die Erklärungen.

Ich habs jetzt einigermaßen verstanden.