3 ms·
call stack growth only matters in languages that don’t have a way to recover gracefully from call stack overflow, e.g. C. You want to convert recursive impleme
by CyberRabbi 6y ago
call stack growth only matters in languages that don’t have a way to recover gracefully from call stack overflow, e.g. C.
You want to convert recursive implementations into iterative implementations in those languages because you can actually handle malloc() failing instead of corrupting your call stack.
You’re right that you’re still implementing a stack no matter what, just moving it from the call stack to the heap.
- jpcooper 6y agoYes. My in-order tree traversal example corresponded to how I would implement it in a C-like language. As long as the person setting the question can confirm that the maximum depth is well below the stack size, it stays recursive, though. By the way, Haskell has stack problems as well when evaluating thunks. Hence the strict foldl’. https://wiki.haskell.org/Stack_overflow https://wiki.haskell.org/Stack_overflow
- CyberRabbi 6y agoRight... probably nearly every language has a poor call stack overflow recovery story, not only because of non-heap stacks but I don’t think it’s relatively straightforward to get the program back into a well defined state after call stack overflow. Those errors can happen on any line of code so unless every line of code is guaranteed to be atomic and a coherent state can be derived from the intermediate states, the program will be in an undefined state.