Search code examples
javascripttail-call-optimization

Is this a tail call? (Javascript)


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?


Solution

  • 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.