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?
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.
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.
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With