4 ms·
> "Why not just use recursive functions" One great reason not to use recursive functions for traversing trees is that you can allocate your own stack data stru
by Retr0id 2y ago
> "Why not just use recursive functions"
One great reason not to use recursive functions for traversing trees is that you can allocate your own stack data structure rather than relying on the call stack itself. In most languages/runtimes, the call stack has a maximum depth which limits the depth of trees you can process, usually on the order of thousands of stack frames.
Managing your own stack usually produces weirder looking code (personally I find "naive" recursive approaches more readable) - but having it as a first-class language feature could solve that!
- cobbal 2y agoIf we're fixing the language, may as well fix the real problem and not artificially limit stack space.
- Retr0id 2y agoThe language doesn't get much of a say, stack limits are usually inherited from the OS itself. It's fixable by not using the OS-provided stack but that's a much more invasive change than a new syntax/stdlib feature.
- worthless-trash 2y agoThe compiler/language absolutely gets a say in this, you can do tail call recursion without stack saturation.
- Retr0id 2y agoTail call elimination is an optimisation that is only possible for certain code patterns. How would you write a tail-recursive tree walk, without using a separate stack or queue data structure to store state?
- worthless-trash 2y agoChallenge accepted, I'll do it over my next long weekend.