4 ms·
Could also be solved if the compiler supported Tail calls optimization
by likeabbas 5y ago
Could also be solved if the compiler supported Tail calls optimization
- dnautics 5y agoI don't think tail call will help depth-first ("obvious recursive way") tree algos.
- aidenn0 5y agoIt doesn't help with breadth-first searches either. A non-degenerate tree of depth N will use O(N) space, and that space will be on the call-stack if you use a recursive algorithm to access it. As long as you use less than 1 page per activation record though, most modern libc implementations behave safely under unbounded recursion as they will allocate a guard-page around each stack. [edit] It would also be useful if the compiler could warn about activation records larger than 1 page. Absent alloca (and deprecated c99 VLAs), that should be statically knowable.
- Dylan16807 5y agoWhat does a recursive breadth-first search look like? I think you'd have to contort yourself to write that, which is why people are specifically mentioning depth-first where recursion is easy and natural.
- aidenn0 5y agoAh you're right; the most natural BFS would be tail-recursive or iterative.
- dnautics 5y agoA BFS is essentially a while loop with a queue datastructure. This is (relatively) easy to implement in TCO-recursive erlang/elixir, which is what I'm currently most proficient in. And, yeah, TCO would help.
- cryptonector 5y agoTCO is an optimization. It's not always possible.
- jhgb 5y agoIt's a misnomer. It's not just "an optimization"; in some cases, it alters program semantics.
- cryptonector 5y agoUsually the only visible side-effect of TCO is stack trace compression and failure to exhaust the stack. You can call that semantics if you like, but I think most people wouldn't. It's absurd that Java doesn't do TCO because of the stack compression "issue" (as I understand, that's why Java doesn't TCO).
- jhgb 5y agoTermination instead of divergence definitely is a change in semantics.
- cryptonector 5y agoNo, failure to fail is not a change in semantics. EDIT: "My program used to fail with a stack size exhaustion error, but now it works -- I'm so angry about this!" -no one ever.
- jhgb 5y agoBut they'd complain about the opposite -- for example if the program were an external-event-driven state automaton.
- cryptonector 5y agoTCO does not do the opposite. TCO helps avoid stack exhaustion without introducing new faults. TCO might cause your program to avoid one stack exhaustion fault only to reveal a different fault (possibly a different stack exhaustion fault). This is not a semantics change. And it's not a bug either.
- Jensson 5y agoThe main reason to use recursion is to use the stack variables, when tail call optimization is possible people usually just prefers loops.