3 ms·
Natural recursion that stems from data structures will be tail-recursive if they themselves are recursive in this manner. Thus e.g. walking a linked list is a p
by int_19h 4y ago
Natural recursion that stems from data structures will be tail-recursive if they themselves are recursive in this manner. Thus e.g. walking a linked list is a problem that naturally translates to tail recursion, but walking a binary tree isn't.
But also, part of the reason why you don't see much deeply recursive code in the wild is because there's no guarantee that it'll be tail-call-optimized, which means that it'll likely fail on large inputs, and will be written iteratively to begin with.
- MrJohz 4y agoEven many operations performed on a linked list will not be tail recursive if you do them naively. For example, a naive sum function might look like: const sum = (node: Node): number => { if (!node.tail) return node.value; return node.value + sum(node.tail); } Even if tail call optimisation were a thing, I'd still expect most recursive functions to be written in a non-tail-recursive fashion, and only later optimised to be tail recursive. But in practice, it's already possible to rewrite those functions in an imperative way when they do become a performance issue. So in practice, I can see why implementors don't prioritise TCO in Javascript, coming from both directions: there's not a lot of free wins available, because tail calls are rarely the most natural way to express a recursive algorithm; and even if you want to explicitly optimise for them, there's already plenty of ways to optimise an inefficient recursive algorithm if that's necessary. That said, I can see the value a lot more in a language that's being used as a compilation target, which it probably made more sense when there was more buzz around compile-to-JS languages, and why it makes more sense now with WebAssembly.