3 ms·
TCO is about more than self-recursive calls -- you should be able to handle mutual recursion: f = x => x > 0 ? g(x - 1) : 0; g = x => x > 0 ? f(x - 1)
by vitus 3y ago
TCO is about more than self-recursive calls -- you should be able to handle mutual recursion:
f = x => x > 0 ? g(x - 1) : 0;
g = x => x > 0 ? f(x - 1) : 0;
(These functions don't do anything other than stress-test the stack, then return 0.)
Note that if I changed this to, say, 1 + g(x - 1), this would no longer fall under the purview of tail recursion, where the last instruction before the return is a recursive call.
The usual workaround I learned in my SICP days was to add a second variable for accumulating any results. And, indeed, that's how the blog post rewrites the recursive function.
(The recursive one-liner is still wildly inefficient because JS doesn't implement arrays as linked lists, so the spread operator results in a copy for each recursive call, resulting in a quadratic solution. It could be made more efficient by using Array.prototype.push, but then it's no longer a pure function.)
- runarberg 3y agoI don’t think they picked the best example to showcase this, most JavaScript developers would write this simply as: Array.from({ length: n }, (_, i) => i + 1) But this example does get the point across, so I think it is fine. I do agree though, while reading it the inefficientness was screaming at me.