Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 473
pixelmike Avatar asked Jun 09 '15 21:06

pixelmike


People also ask

What is tail call in JavaScript?

A proper tail call is when the last thing a function does is return the result of calling another function. In the above function the highlighted ternary else returns the result of n * factorial(n - 1), in other words not a standalone function, and as a result would need to retain the stack.

How do you know if something is tail recursive?

A function is tail-recursive if it ends by returning the value of the recursive call. Keeping the caller's frame on stack is a waste of memory because there's nothing left to do once the recursive call returns its value.

Does JavaScript do tail call optimization?

Javascript does not optimize tail calls, so I implemented tail call optimization in Javascript itself, and tested it on various browsers. For those not familiar with tail calls, the first two sections explain it.

Is tail a recursion?

Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. For example the following C++ function print() is tail recursive.


1 Answers

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.

like image 68
Bergi Avatar answered Sep 23 '22 05:09

Bergi