You know, this is the canonical programmer missing the forest by arguing the shape of the leaf on a tree. The point is to discuss the mechanism, and factorial happens to be a ridiculously simple example.
Perhaps what the article needs is a disclaimer such as:
We can easily rewrite this in iterative style, but there are other functions that aren’t so amenable to rewriting and using a simple example allows us to concentrate on the mechanism rather than the “domain.”
I found your post interesting (just like all your other posts), but for me where this one falls short is the lack of real life examples. I mean I understand why this would be good for calculating factorials and other kinds of recursive math, but how often does the average javascript programmer need to do that anyway? How can I benefit from this to write better code in practise, and not just in theory? To me this is far less obvious than with, for example, your article on decorator functions [0].
Trampolining is one way to implement "tail call optimisation". This basically means that when the last instruction (the "tail") of a function is a call to another function (possibly the same one, recursively), then we can perform an optimisation: rather than "going down" into the function (adding a new stack frame) we can run it where we already are (in our current stack frame). This optimisation is possible because we know that we don't need our current stack frame anymore, since this is the last instruction.
Ever find yourself writing a "main loop" full of unrelated code which only appears in the same place because you're forced to keep it all between the loop's braces? That's a prime candidate for mutual recursion, made safe using tail-call optimisation:
var foo = function() {
//
};
var bar = function() {
//
};
var baz = function() {
//
};
var main = function() {
while (true) {
foo();
bar();
baz();
}
};
main();
Can be replaced with:
var foo = function() {
//
bar();
};
var bar = function() {
//
baz();
};
var baz = function() {
//
foo();
};
foo();
This is how I tend to write Javascript; although I generally handle tail-call optimisation by using setTimeout(foo, 0), which has the same effect.
Not the same effect. setTimeout() will execute the callback after the main event loop has completed, potentially allowing the browser to reflow the page, etc. Doing that will slow things down considerably with lots of callbacks.
Exactly. My point is that the factorial function is always used as an example when discussing tail call optimization and TCO is useless for it. I get how this is useful. I just would love to see an example of actually using it for something other than calculating factorials.
I understand this sentiment, but what simple zero-context function would you choose in place of factorial? You'd want something that's trivially and naturally recursive that doesn't also act on non-primitive types (to avoid having to do a bunch of blahblah introducing the particulars of a given data structure).
How about merge sort or quicksort? Or maybe a binary search? Seems a little more real-worldy. I suppose factorial is a good starting point to illustrate how to construct the function, but an example or two of an actual use case would be so so great.
You might. The problem with doing a binary search in a while loop is that now you have to actually maintain your own stack, which to me seems like it should be left to the runtime. The point of using a recursion is that you can do the same thing as a loop but with less code.
Mostly, the problem is that no developer in the last 10 years has ever had to write an efficient factorial function except in a job interview or for a blog post. That is slightly less the case with sorts and searches.
Agreed -- I would love to see an example of a binary tree.
As a matter of fact, I was struggling with Stack Overflow problems when constructing huge kd-trees recursively. I read this article a week ago, but failed to translate the pure recursive formulation of constructing a tree into a tail-recursive one -- since the recursion goes two ways instead of one
Here's an example from Wikipedia:
function kdtree (list of points pointList, int depth)
{
// Select axis based on depth so that axis cycles through all valid values
var int axis := depth mod k;
// Sort point list and choose median as pivot element
select median by axis from pointList;
// Create node and construct subtrees
var tree_node node;
node.location := median;
node.leftChild := kdtree(points in pointList before median, depth+1);
node.rightChild := kdtree(points in pointList after median, depth+1);
return node;
}
Not really the point, the point is to gain explicit control over the call stack so you can have more flexibility. Also I would not really call it a hack, it's something you can do with many languages that support higher-order functions.
