Is this a tail call? (Javascript)

2019-04-08 03:34发布

问题:

Supose you have a recursive function like:

Blah.prototype.add = function(n) {
    this.total += n;
    this.children.forEach(function(child) {
        child.add(n);
    });
};

Is the child.add() a tail call? If not can it be written so it is?

回答1:

Yes, it is a tail call:

function(child) {
    child.add(n);
// ^ tail
}

Yet nothing here is tail-recursive, because it's not a direct recursive call.

Also this.children.forEach(…) is a tail call within the add method.

However, the invocation of the callback within the native forEach method is probably not tail-call optimised (and all but the last one cannot be anyway). You can force it by rewriting your function to

Blah.prototype.add = function(n) {
    "use strict";
    this.total += n;
    let l = this.children.length;
    if (!l--)
        return;
    for (let i=0; i<l; i++)
        this.children[i].add(n);
    this.children[i].add(n); // tail-recursion
};

Notice that none of these tail calls will be optimised if you don't also return their results.



回答2:

Are any Javascript engines tail call optimized?

JavaScript as it is currently will not optimise for that

Another option would be a trampoline https://taylodl.wordpress.com/2013/06/07/functional-javascript-tail-call-optimization-and-trampolines/