Is this a tail call? (Javascript)

Question

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?

I would say so. Even though it is inside a loop, it's still the last action being performed. — Brennan, Jun 09 '15 at 21:20
I wasn't sure... I was thinking about a traditional `for(i=0;i — pixelmike, Jun 09 '15 at 21:25
Presumably a `tail call` in JS would make the use of `return someFn()` allowing also the initator function to be garbage collected. — Roko C. Buljan, Jun 09 '15 at 21:25
forEach() won't see items pushed into the array while it's being iterated... — dandavis, Jun 09 '15 at 21:30
It's a tail call within the callback function, but `forEach` still needs to keep its looping state. So there's effectively little difference in stack usage between this and a `for` loop. — Barmar, Jun 09 '15 at 21:32
@pixelmike You can just re-write as an iterative algorithm if you are unsure about it ;) — plalx, Jun 09 '15 at 21:55
@plalx Ha, I was actually thinking about a use case in traversing a scene graph hierarchy. Perhaps that could be flattened into a loop though and the example is too contrived. I'm just trying to think through some of this stuff. — pixelmike, Jun 10 '15 at 00:19

score 1 · Answer 1 · edited May 23 '17 at 12:30

1

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/

edited May 23 '17 at 12:30

Community

1
1

answered Jun 09 '15 at 21:40

exussum

18,275
8
32
65

Yeah, I didn't think the optimization was in place yet, but I'm trying to prepare for when it is. Thanks for the links. – pixelmike Jun 09 '15 at 21:49
That question you linked is outdated. ES6 is having proper tail call optimisation. – Bergi Jun 09 '15 at 21:51
Assuming its correct http://kangax.github.io/compat-table/es6/ nothing makes use of it as of today – exussum Jun 09 '15 at 21:57
@exussum: Yes, the draft isn't accepted yet, but all the features are already gradually being implemented in the engines. And as you can see, some transpilers already have optimisations in place. – Bergi Jun 09 '15 at 22:00
While I agree the link is still in date. Early adoptions can change but nothing has tail optimisation in. There could be syntax changes to allow tail call optimisation yet. Its unknown and unless you follow the drafts its impossible to make an implementation – exussum Jun 09 '15 at 22:03
ES5 definitely does not have tail-call optimization but ES6 will do. It's a part of the specification :) – TaoPR Jun 09 '15 at 23:00

Bergi · Accepted Answer · 2017-07-26T11:14:22.363

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.

edited Jul 26 '17 at 11:14

answered Jun 09 '15 at 21:56

Bergi

630,263
148
957
1,375

Are you sure `add` is tail-recursive? Even if a simple for loop construct was used, the latest operation executed would be the loop conditional check, hence wouldn't be tail-recursive, no? I thought the recursive call had to be the latest executed expression for an algorithm to be tail-recursive. – plalx Jun 09 '15 at 22:02
@plalx: I didn't say `add` was tail-recursive. If at all it was mutually recursive with `forEach` and its callback - it does not call itself. I only said that `add` contains a tail call. – Bergi Jun 09 '15 at 22:06
Thanks, yes I should have been clear that I was asking if child.add was a tail call for the add function, not the forEach callback. – pixelmike Jun 09 '15 at 23:51
@pixelmike: A call can be in a tail position only relative to the currently executing function. Functions elsewhere on the call stack or in the lexical scope do not matter. – Bergi Jun 10 '15 at 00:01
[Rauschmayer disagrees](http://exploringjs.com/es6/ch_tail-calls.html#_pitfall-solo-function-calls-are-never-in-tail-position) (you have to scroll up slightly, the banner at the top obscures the target). Can you point to where in the spec it defines that `child.add(n)` is in tail position for the `forEach` callback? – T.J. Crowder Jul 26 '17 at 10:38
@T.J.Crowder It's right, the spec only defines the tail call optimisation for calls whose results are directly `return`ed. I'm not sure whether informally we can say "tail call" for the last executed *expression* in a function body, or maybe I was just distracted by other languages (Scala, Ocaml) that implicitly return the last expression. In theory, in a strictly typed language we could optimise Unit-returning functions, in JS we still could replace the current stack frame by a "`void`" one of which only one is needed even for multiple nested calls. – Bergi Jul 26 '17 at 11:13
So no, `child.add(n)` isn't a tail call (by the spec), though it *could* be in some situations (including this one) if it were specified that way. Not that it matters much in the example anyway, as you said. :-) – T.J. Crowder Jul 26 '17 at 11:52

Is this a tail call? (Javascript)

2 Answers2

Linked