Was ist Tail recursion?

In der Computerprogrammierung ist Tail-Rekursion die Verwendung eines Tail-Aufrufs, um eine rekursive Funktion auszuführen. Ein Endaufruf ist, wenn eine Funktion als letzter Akt einer anderen Funktion aufgerufen wird. Zum Beispiel in diesem JavaScript-Programm:

var myTailFunc = function (myVar) { 
  return myVar; 
}; 
var myFunc = function (myVar) { 
  return myTailFunc(myVar); 
};

Hier ist der Aufruf von myTailFunc(myVar) ein Tail-Aufruf, weil es die letzte Operation von myFunc(myVar) ist. Wenn der Compiler sieht, dass dies die letzte Operation von myFunc ist, kann er eine kleine Optimierung durchführen. Im Wesentlichen muss es keine Rücksprungadresse auf den Stack schieben, da es nicht zu myFunc zurückkehren muss. Es kann den Rückgabewert von myTailFunc als Rückgabewert von myFunc zurückgeben.

Diese kleine Optimierung wird bedeutsamer, wenn sie in einer rekursiven Funktion verwendet wird. Normalerweise würde jede Rekursionsebene erfordern, dass eine zusätzliche Rücksprungadresse auf den Stapel geschoben wird. Die Schwanzrekursion macht dies unnötig.

Hier ist ein Beispiel für eine einfache faktorielle JavaScript-Funktion, die zuerst ohne und dann mit Schwanzrekursion geschrieben wurde.

Fakultätsfunktion ohne Schwanzrekursion

var factorial = function (n) { 
  if (n == 0) { 
    return 1; 
  } else { 
    return n * factorial (n - 1); 
  } 
};

Diese Funktion ist rekursiv, aber nicht endrekursiv. Der letzte Prozess der Funktion ist die Multiplikationsoperation (“*”), daher muss die Rekursion immer zur aufrufenden Funktion zurückkehren.

Fakultätsfunktion mit Schwanzrekursion

var factorial = function (n) { 
  var recursion = function (n, subTotal) { 
    if (n == 0) { 
      return subTotal; 
    } else { 
      return recursion(n - 1, n * subTotal); 
    } 
  }; 
  return recursion(n, 1); 
};

Funktion, Programmierbegriffe