Seite 4: Endrekursion

Inhaltsverzeichnis

Endrekursion

Die Endrekursion, auch als "Tail Recursion" bezeichnet, ist ein Verfahren zur Optimierung von rekursiven Funktionsaufrufen. Es lässt sich anwenden, wenn der letzte Funktionsaufruf innerhalb der rekursiven Funktion sie selbst ist.

Die Idee dahinter ist, in einem solchen Fall den zusätzlichen Funktionsaufruf zu streichen und die aktuelle Instanz der Funktion samt dazugehörigem Stack wiederzuverwenden. Auf die Art erspart die Endrekursion den aufwendigen Aufbau eines neuen Stacks, den Aufruf einer neuen Funktion samt abschließendem Abbau des erzeugten Stacks.

Bei rekursiven Funktionen, die mit Endrekursion optimiert werden, kann zudem kein Stack Overflow auftreten. Das gehört bei rekursiven Funktionen zu einem der Standardfehler, nämlich wenn die Tiefe der Rekursion zu groß wird und die Verwaltungsinformationen überhand nehmen.

Ein Nachteil von Endrekursion sei jedoch nicht verschwiegen: Sie erschwert das Debuggen einer durch sie optimierten Funktion bedeutend, da die Aufrufreihenfolge und der dazugehörige Call Stack nicht mehr erkennbar sind. Schließlich wird letztlich nur durch die immer gleiche Instanz der Funktion iteriert.

Als Beispiel soll an der Stelle die Methode Sum (in Pseudocode) dienen, die die ersten x natürlichen Zahlen summiert:

function int Sum(int x)
{
    if(x == 0)
    {
        return 0;
    }
    else
    {
        return x + Sum(x ? 1);
    }
}

Die Funktion ist zwar rekursiv, nicht jedoch endrekursiv: Als letzte Anweisung innerhalb der Funktion wird nämlich nicht, wie man auf den ersten flüchtigen Blick erwarten könnte, die Funktion rekursiv aufgerufen, sondern x zum Ergebnis des rekursiven Funktionsaufrufs addiert. Sum lässt sich jedoch in eine endrekursive Variante umwandeln, die das Assoziativgesetz ausnutzt:

function int Sum(int x)
{
    return SumInternal(0, x);
}

function int SumInternal(int x, int y)
{
    if(y == 0)
    {
        return x;
    }
    else
    {
        return SumInternal(x + y, y - 1);
    }
}

Daraus ergibt sich folgender Ablauf für beispielsweise den Aufruf von Sum(5):

Sum(5) -> SumInternal(0, 5) -> SumInternal(5, 4) -> SumInternal(9, 3) 
-> SumInternal(12, 2) -> SumInternal(14, 1) -> SumInternal(15, 0) 
-> 15


(ane)