Ich habe versucht zu verstehen Tail call optimization
im Kontext von JavaScript und habe die folgenden rekursiven und schwanzrekursiven Methoden für geschrieben factorial()
.
Rekursiv:
function factorial (n) {
if (n < 2) {
return 1;
} else {
return n * factorial(n-1);
}
}
Schwanzrekursiv:
function factorial (n) {
function fact(n, acc) {
if (n < 2) {
return acc;
} else {
return fact(n-1, n * acc);
}
}
return fact(n, 1)
}
Ich bin mir jedoch nicht sicher, ob die tail-recursive
Version der Funktion vom JavaScript-Compiler optimiert wird, da sie in anderen Sprachen wie Scala usw. ausgeführt wird. Kann mir jemand dabei helfen?
quelle
Theoretisch ja. Wie die andere Antwort besagt.
In der Praxis wird dies jedoch ab Juli 2017 nur von Safari unterstützt.
Kompatibilität mit Javascript ES6 (ES2015): https://kangax.github.io/compat-table/es6/
quelle
Wie die anderen Antworten gesagt haben, nicht in der Praxis. Sie können jedoch ein Hilfsprogramm definieren, das Ihnen hilft.
class Tco { constructor(func) { this.func = func; } execute() { let value = this; while (value instanceof Tco) value = value.func(); return value; } } const tco = (f) => new Tco(f);
function factorial (n) { const fact = (n, acc) => tco(() => { if (n < 2) { return acc; } else { return fact(n-1, n * acc); } }); return fact(n, 1).execute(); } console.log(factorial(2000000)); // Infinity
Wie Sie sehen können, können Sie damit rekursive Endfunktionen mit nur geringem Unterschied in der Syntax schreiben, ohne dass ein maximaler Aufrufstapelfehler auftritt.
quelle