It depends on whether the limited call stack capacity will be an issue for the particular problem you’re solving.
I’m presently working on a problem which uses traversal of TypeScript file syntax trees.
I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow.
A manually managed stack might seem safer, but as pointed out by this article the code would be more complicated and, in my case, for no good reason.
swiftcoder 1 hours ago [-]
This has always felt like the kind of thing we could be building compilers to solve. Recursive -> explicit stack is a very mechanical conversion, why can't we write a compiler transform pass that does that rewrite any time it detects a high potential for stack overflow?
derriz 9 minutes ago [-]
It’s called TCO - tail call optimization - and gcc and llvm are supposed to implement it although tail recursive style code is probably uncommon in C or C++. Outside of that it’s common in functional languages where recursive functions are obviously idiomatic and so it has more potential to provide performance benefit.
It’s not a purely local optimization - affecting the call structure so debugging is a pain point. Which is probably why most imperative language compilers don’t bother given the lack of utility for the vast majority of code bases.
It feels like something that would need to be specified at the language spec or semantics level to make it useful rather than just making it optional for the compiler - otherwise the developer is probably just going to do the transform manually - to be safe - if stack explosion was a possibility if the compiler decided on a whim to not perform TCO.
Epa095 13 minutes ago [-]
Yeah, tail call elimination, is definitely doable.
Python famously does not have it because "Language inventor Guido van Rossum contended that stack traces are altered by tail-call elimination making debugging harder, and preferred that programmers use explicit iteration instead".
https://en.wikipedia.org/wiki/Tail_call
Jaxan 27 minutes ago [-]
Many compilers do change a recursion into a loop, avoiding the stack altogether!
Rendered at 10:47:51 GMT+0000 (Coordinated Universal Time) with Vercel.
I’m presently working on a problem which uses traversal of TypeScript file syntax trees.
I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow.
A manually managed stack might seem safer, but as pointed out by this article the code would be more complicated and, in my case, for no good reason.
It’s not a purely local optimization - affecting the call structure so debugging is a pain point. Which is probably why most imperative language compilers don’t bother given the lack of utility for the vast majority of code bases.
It feels like something that would need to be specified at the language spec or semantics level to make it useful rather than just making it optional for the compiler - otherwise the developer is probably just going to do the transform manually - to be safe - if stack explosion was a possibility if the compiler decided on a whim to not perform TCO.
Python famously does not have it because "Language inventor Guido van Rossum contended that stack traces are altered by tail-call elimination making debugging harder, and preferred that programmers use explicit iteration instead". https://en.wikipedia.org/wiki/Tail_call