Endrekursion

Eine rekursive Funktion ist endrekursiv (tail recursive), wenn der rekursive Funktionsaufruf die letzte Aktion ist, welche ausgeführt wird, bevor die Funktion verlassen wird.

Der Vorteil der Endrekursion ist, dass sie gegenüber einer 'normalen' Rekursion stets die gleiche Menge an Speicherplatz benötigt. Die Komplexität für den Speicherbedarf beträgt also O(1), was als sehr effizient gilt. Leider beherrschen nicht alle Programmiersprachen die Endrekursion. Manche Sprachen behandeln sie wie die normale Rekursion, was zu einem linearen Anstieg des Speicherplatzes während der Ausführung führt, also zu O(n). Unter den Sprachen, die keine Endrekursion beherrschen, sind so bekannte wie C und seine Derivate C++ und C# sowie Java.

Beispiel

Gegeben sei die rekursive Funktion sum, die die Summe der ersten n natürlichen Zahlen berechnet (siehe das Beispiel unter Rekursion):

sum(n)
   if n=0
     return 0
   else
     return n + sum(n-1)

Diese Funktion macht den Anschein endrekursiv zu sein, aber bei genauerer Betrachtung stellen wir fest, dass nicht der rekursive Funktionsaufruf die letzte Aktion darstellt, sondern die Addition. Also schreiben wir die Funktion so um, dass der rekursive Aufruf zur letzten Aktion wird:

sum(n)
 if n=0
    return 0
 else
    return sum (0, n)

sum(n,m)
 if m=0 
   return n
 else
   n=n+m
   return sum (n, sum(m-1))

Natürlich kann auch eine endrekursive Funktion, wie jede rekursive Funktion in eine Iteration überführt werden:

sum(n)
   m := 0
   
   while (n > 0) do
     m   := m + n
     n   := n - 1
   end-while
   return m

Rekursive- und iterative Lösungen stellen meistens eine direkte Umsetzungen eines Problemes dar, welches Schrittweise analysiert wurde. Die Effizienz in der Ausführungszeit leidet dabei oft massiv. Deshalb lohnt es sich vielfach effizientere Algorithmen für ein Problem zu suchen. So ist der beste Algorithmus zur Berechnung des Beispielfalles vor allem durch die "Gaußsche Schulgeschichte" bekannt geworden:

sum(n) = (n*(n+1)) / 2

Verallgemeinerung

Allgemein ist eine Funktion f endrekursiv, wenn sie sich auf folgende Weise definieren lässt:

$f(x)={\begin{cases}f(r(x)),&{\mbox{falls }}R(x)\\s(x),&{\mbox{sonst }}\end{cases}}$

Dabei sind r und s beliebige nicht mittels f definierte Funktionen und R die negierte Abbruchbedingung.