JavaScript-Tail-Rekursion

1. Verwendung von Tail-Rekursion
2. So implementieren Sie Tail-Rekursion in JavaScript

Endrekursion ist ein Programmierkonzept, das eine Funktion beinhaltet, die sich selbst als letzte Aktion aufruft, die sie ausführt. Dies kann eine nützliche Technik zum Optimieren bestimmter Algorithmen sein, da es der Funktion ermöglicht, ihren Stapelrahmen wiederzuverwenden, anstatt bei jedem Aufruf einen neuen zu erstellen.

Dies kann dazu beitragen, die Menge an Speicher zu reduzieren, die das Programm verwendet, und seine Leistung zu verbessern.

In JavaScript wird die Tail-Rekursion nicht nativ unterstützt, aber es gibt einige Möglichkeiten, dies mit verschiedenen Techniken zu erreichen. Schauen wir uns genauer an, was Tail-Rekursion ist, wie sie funktioniert und wie sie in JavaScript implementiert wird.

Verwendung von Tail-Rekursion

Es gibt einige Gründe, warum Tail-Rekursion in bestimmten Situationen nützlich sein kann:

1. Speichereffizienz: Wenn sich eine Funktion rekursiv selbst aufruft, erstellt sie für jeden Aufruf einen neuen Stapelrahmen. Dies kann viel Speicher verbrauchen, insbesondere bei tief verschachtelten rekursiven Aufrufen.

   Die Schwanzrekursion ermöglicht es der Funktion, ihren Stapelrahmen wiederzuverwenden, wodurch die vom Programm verwendete Speichermenge reduziert wird.

2. Leistung: Tail-Rekursion kann auch in Bezug auf die Leistung effizienter sein, da sie es der Funktion ermöglicht, den Aufwand für das Erstellen und Zerstören mehrerer Stack-Frames zu vermeiden. Dadurch kann die Funktion insbesondere bei großen Eingabewerten schneller ausgeführt werden.

3. Einfachheit des Codes: Die Schwanzrekursion kann den Code auch leichter verständlich machen, da sie die Notwendigkeit einer expliziten Schleife oder iterativen Struktur eliminiert. Dies kann den Code prägnanter und leichter lesbar machen.

So implementieren Sie Tail-Rekursion in JavaScript

Wie bereits erwähnt, unterstützt JavaScript nativ keine Schwanzrekursion. Es gibt jedoch einige Möglichkeiten, dies mit verschiedenen Techniken zu erreichen.

Beispiel 1

Ein Ansatz besteht darin, die ES6-Syntax für Funktionsargumente zu verwenden, mit der Sie Standardwerte für Funktionsparameter angeben können. Dies kann verwendet werden, um eine einfache Wrapper-Funktion zu implementieren, die die Tail-Rekursion für Sie handhabt.

function factorial(n, result = 1) {
  if (n === 1) {
    return result;
  } else {
    return factorial(n - 1, n * result);
  }
}
console.log('Factorial of 5 is ' + factorial(5));

Ausgang:

Factorial of 5 is 120

In diesem Beispiel erhält der Parameter Ergebnis den Standardwert 1. Wenn er also beim Aufruf der Funktion nicht angegeben wird, wird er standardmäßig auf 1 gesetzt. Dadurch können wir eine einfache Wrapper-Funktion erstellen, die factorial aufruft, wobei der result-Parameter auf 1 gesetzt ist, was die Schwanzrekursion für uns übernimmt.

Beispiel 2

Ein anderer Ansatz ist die Verwendung der Eigenschaft arguments.callee, die auf die aktuell ausgeführte Funktion verweist. Dies kann verwendet werden, um eine rekursive Funktion zu implementieren, die sich selbst als letzte Aktion aufruft, die sie ausführt, wie unten.

function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * arguments.callee(n - 1);
  }
}
console.log('Factorial of 5 is ' + factorial(5));

Ausgang:

Factorial of 5 is 120

Dieser Ansatz funktioniert, hat aber einige Nachteile. Erstens ist die Eigenschaft arguments.callee im Strict-Modus veraltet, sodass ihre Verwendung Probleme verursachen kann, wenn Sie den Strict-Modus in Ihrem Code verwenden.

Zweitens kann die Eigenschaft arguments.callee durch anderen Code überschrieben werden, was zu unerwartetem Verhalten führen kann.

Beispiel 3

Ein dritter Ansatz besteht darin, eine Trampolin-Funktion zu verwenden, eine Funktion höherer Ordnung, die eine rekursive Funktion umschließt und ermöglicht, dass sie auf schwanzrekursive Weise aufgerufen wird. Um eine Trampolinfunktion zu implementieren, können Sie das folgende Muster verwenden:

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

function factorial(n, result = 1) {
  if (n === 1) {
    return result;
  } else {
    return () => factorial(n - 1, n * result);
  }
}
console.log('Factorial of 5 is ' + trampoline(factorial(5)));

Ausgang:

Factorial of 5 is 120

In diesem Beispiel ist die Funktion factorial in endrekursiver Weise geschrieben, wobei der rekursive Aufruf die letzte Aktion ist, die ausgeführt wird, bevor die Funktion zurückkehrt. Die trampoline-Funktion umschließt dann die factorial-Funktion und verarbeitet die rekursiven Aufrufe für uns, sodass wir factorial auf schwanzrekursive Weise aufrufen können.

Die Verwendung einer Trampolin-Funktion kann etwas komplexer sein als die anderen Ansätze, hat aber den Vorteil, dass sie effizienter und weniger fehleranfällig ist.