Rekursion

Rekursion setzt für die Lösung eines Problems darauf, dass die gleiche Funktion immer wieder von sich selbst aufgerufen werden kann. Beispiele für die Verwendung von Rekursion kann die mathematische Summe sein, Fakultätsfunktion oder Zahlenreihen, die rekursiv angegeben worden.

Semantisch ist die Rekursion gleichbedeutend mit der Iteration (Schleife, Wiederholung), allerdings gibt es Fälle, wo eine Rekursion effizienter oder einfacher (zu formulieren) ist.

Theorie

Als rekursive Funktion wird eine Funktion bezeichnet, die sich selbst aufruft. Um zu einem Ergebnis zu kommen, wird ein Rekursionsschluss benötigt, also eine Bedingung, die, wenn sie erfüllt ist, den rekursiven Abstieg beendet und den Aufstieg beginnt.

Nehmen wir eine mathematische Summe:

sum{i=0}{n}{i}

Diese Summe berechnet die Summe aus allen i von 0 bis n. Formuliert man das als Iteration in C, könnte das folgendermaßen aussehen:

int ergebnis=0;
for (int i=0; i<n; i++)
{
    ergebnis=ergebnis+i;
}

Nehmen wir die Summe allerdings auseinander, so erhalten wir schrittweise folgendes: sum{i=0}{n}{i} = sum{i=0}{n-1}{i} + n = sum{i=0}{n-2}{i} + (n-1) + n = 0 + 1 + 2 + ... + (n-2) + (n-1) + n

Das heißt, wie definieren uns eine Funktion sum(int n) die alle Zahlen von 0 bis n berechnet. Dann können wir für alle Summen mit größerem Endwert als n diese Funktion nutzen.

int num ( int n )
{
    // Abbruch der Rekursion, wenn n bei 0 angekommen ist
    if (n<=0)
        return 0;
    
    // ansonsten: n>0
    return n + sum (n-1);
}

Die Funktion addiert das übergebene n und addiert die Summe von 0 bis n-1 hinzu. Dabei setzt der nächst tiefere Funktionsruf wiederum eine Addition von n-1 mit der Summe von 0 bis n-2 ein. Das passiert so weiter bis n irgendwann auf 0 gefallen ist, und damit 0 zurückgegeben wird. Wir erhalten also schrittweise:

sum (n) = n + sum(n-1) = n + (n-1) + sum(n-2) = ... = n + (n-1) + (n-2) + ... + 2 + 1 + 0

Weitere Beispiele

Fakultätsberechnung

Die mathematische Fakultät ist folgendermaßen definiert:

n! = 1 * 2 * 3 * ... * (n-1) * n = prod{i=1}{n}{i}

Eine rekursive Umsetzung dessen könnte wie folgt aussehen (Voraussetzung: n>=0):

int fak ( int n )
{
    if (n <= 1)
        return 1;
 
    return n * fak (n);
}

Zahlenfolge mit rekursiver Bildungsvorschrift

Eine mathematische Zahlenfolge kann ist einer rekursiven Bildungsvorschrift angegeben werden. Das könnte folgendermaßen aussehen:

a_1 = 1
a_2 = 1
a_n = a_{n-1} + a_{n-2}

Eine Umsetzung als C-Funktion könnte so aussehen (Voraussetzung n>=1):

int fib ( int n )
{
    if (n <= 2)
        return 1;
 
    return (fib(n-1) + fib(n-2));
}