2 ms·
It 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
by aidenn0 5y ago
It 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.