Are functions in JavaScript tail-call optimized?
JavascriptRecursionTail RecursionJavascript Problem Overview
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?
Javascript Solutions
Solution 1 - Javascript
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.
Solution 2 - Javascript
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/
Solution 3 - Javascript
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.
Solution 4 - Javascript
Safari is the only browser that supports tail call optimization. ES2015 offers tail call optimization in strict mode
function factorial(n, returnVal= 1) {
'use strict';
if (n <= 1) return returnVal;
return factorial(n - 1, n * returnVal);
}
factorial(555)
Follow the LINK