Rekursion -

1.1 Allgemeines zu Rekursionen Die Rekursion ist ein fundamentales Konzept, das in der Mathematik und in der Informatik im Einsatz ist. Zerlegt man ein Problem in Teilprobleme und erhält dann wieder das Problem von dem ausgegangen wurde, so handelt es sich hierbei um eine Rekursion.
Dies funktioniert so, das sich eine Funktion immer wieder selbst aufruft, und das Problem wieder in Teilprobleme zerlegt wird. Es wird so lange zerlegt, bis das Teilproblem so einfach ist, daß es ausprogrammiert werden kann. Der Funktion muß immer das Problem übergeben werden, welches in Teilprobleme zerlegt wird und dann wieder übergeben wird. Tritt das Problem nicht mehr auf, d.h. ist Abbruchbedingung ist bereits erfüllt wird mit Hilfe eines Rückgabewertes die Rekursion beendet. Ansonsten wird das Ergebnis des Aufrufs für die Berechnung des Rückgabewertes verwendet.









1.2 Beispiele
1.2.1 Ausgabe eines Binärbaumes (sog. Traversierung)
Eine Anwendung auf die Rekursionen regelrecht zugeschnitten sind, sind Binärbäume, deren iterative Programmierung ziemlich aufwendig wäre.



C-Funktion traverse: Es wird solange in den linken Ast des Knotens verzweigt, bis es keinen linken Ast mehr gibt. Dann wird der aktuelle Knoten ausgegeben und in den ev. Vorhandenen rechten Ast verzweigt. Gibt es auch keinen rechten Ast mehr, dann wird in den Knoten der übergeordneten Ebene zurückgegangen. Solange bis der ganze Baum ausgegeben wurde. Die Ausgabe der Knoten erfolgt nach der Numerierung. Der erste Knoten ist logischerweise links unten, dann zu seinem übergeordneten und dann zum untergeordneten rechten Knoten.

void traverse(KNOTEN *pknoten)
{

if(pknoten-left) traverse(pknoten-left);

knoten_ausgeben(pknoten);

if(pknoten-right) traverse(pknot-right);
}


1.2.2 Fakultät einer Zahl
Die Fakultät einer Zahl x ist folgendermaßen definiert: x! = x * (x-1)!. Das wird solange fortgeführt, bis x-n den Wert 1 erreicht hat.
z.B: 5! = 5 * 4 * 3 * 2 *1
C-Funktion factorial: Berechnet die Fakultät einer Zahl.
Lösung mit Rekursion:

int factorial(int x)
{

if(x==1) return 1;

return x * factorial(x-1);
}
Lösung mit Iteration(mit Schleifen):

int factorial( int x)
{

for(int factor=1; x 1; x--) factor = factor * x;

return factor;
}




1.3 Arten von Rekursionen

1.3.1 Lineare Rekursion
Die Tiefe der möglichen Rekursion ist 1. Eine linear - rekursive Funktion ruft sich maximal einmal selbst auf. Diese Funktionen können leicht auch iterativ programmiert werden.


1.3.2 Kaskadenförmige Rekursion
Es kann vorkommen, daß sich die Funktion mehrmals selbst aufruft. Die Bearbeitung von Bäumen ist typischerweise kaskadenförmig und die Adaptierung in iterative Programmierung ist nicht so ohne weiteres möglich.


1.4 Gegenüberstellung Rekursion und Iteration
Grundsätzlich wird bei einer Rekursion die Funktion immer wieder aufgerufen bis die Abbruchbedingung erfüllt ist. Bei der Iteration wird das Problem mit Hilfe von Schleifen gelöst. Theoretisch kann jede(!) rekursive Funktion auch als iterative Funktion ausprogrammiert werden, jedoch gibt es Probleme für die sich die Rekursion besonders gut eignet, zum Beispiel Binärbäume.

Es gibt drei Kriterien:







Kriterium Rekursion Iteration
Laufzeit langsam schneller

Speicher viel wenig
Aufwand gering höher


Ob man nun Rekursionen oder Iterationen verwendet, hängt vom jeweiligen Problem ab und von der Wichtigkeit der jeweiligen Kriterium ab. Wenn es möglich ist, sollte man lineare Rekursionen in Iterationen umwandeln und kaskadenförmige Rekursionen belassen.