Menu
I have been trying to understand Tail call optimization in context of JavaScript and have written the below recursive and tail-recursive methods for factorial().
Recursive:
function factorial (n) {
if (n < 2) {
return 1;
} else {
return n * factorial(n-1);
}
}
Tail-recursive:
function factorial (n) {
function fact(n, acc) {
if (n < 2) {
return acc;
} else {
return fact(n-1, n * acc);
}
}
return fact(n, 1)
}
But I am not sure if the tail-recursive version of the function will be optimised by JavaScript compiler as it is done in other languages like Scala etc. Can someone help me out on this one?
969
As a rule of thumb; tail-recursive functions are faster if they don't need to reverse the result before returning it. That's because that requires another iteration over the whole list. Tail-recursive functions are usually faster at reducing lists, like our first example.
In tail recursion, there is no other operation to perform after executing the recursive function itself; the function can directly return the result of the recursive call. In simple words, in tail recursion, the recursive function is called last. So it is more efficient than non-tail recursion.
The next version of JavaScript (ECMAScript 6) will be introducing an incredibly powerful programming feature called Tail Recursion, a feature that I'm very excited about. In this article I want to talk a bit about recursion vs.
Tail call optimization happens when the compiler transforms a call immediately followed by a ret into a single jmp . This transformation saves one instruction, and more importantly it eliminates the implicit push/pop from the stack done by call and ret .
Update: As of January 1, 2020 Safari is the only browser that supports tail call optimization.
The chromium team explicitly states that Tail Call Optimization is not under active development and can be tracked here.
The implementation for Firefox can be tracked here
Original Post
Yes, ES2015 offers tail call optimization in strict mode. Dr. Axel Rauschmayer lays it out beautifully at the link below so I shall not repeat his words here.
Note: ES 5 does not optimize tail calls.
http://www.2ality.com/2015/06/tail-call-optimization.html
146
In theory yes. As the other answer states.
In practice though, as of July 2017, No. Only Safari supports it.
Javascript ES6 (ES2015) compatability: https://kangax.github.io/compat-table/es6/
31
As the other answers have said, not in practice. However, you can define a utility to help out.
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
As you can see, this allows you to write tail recursive functions with only a small difference in syntax, without running into a max call stack error.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
