JavaScript 尾部调用中的函数是否优化？

我一直试图在 JavaScript 的上下文中理解 Tail call optimization，并为 factorial()编写了以下递归和尾递归方法。

递归:

function factorial (n) {
if (n < 2) {
return 1;
} else {
return n * factorial(n-1);
}
}

尾递归:

function factorial (n) {
function fact(n, acc) {
if (n < 2) {
return acc;
} else {
return fact(n-1, n * acc);
}
}


return fact(n, 1)
}

但是我不确定这个函数的 tail-recursive版本是否会像其他语言(如 Scala 等)那样被 JavaScript 编译器优化。有人能帮帮我吗？

41347 次浏览
小开
最佳答案

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

小开

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/

小开

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.

小开

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


提交答案