3 ms·
Any recursive tree traversal function is incorrect. You need to write the function in an iterative fashion. Hoping that a recursive function won't run out of st
by bjourne 5y ago
Any recursive tree traversal function is incorrect. You need to write the function in an iterative fashion. Hoping that a recursive function won't run out of stack space is like allocating 500 characters to an input field and hoping that the user never will enter longer inputs. Consider a degenerate tree consisting of a linked list of N nodes. If N is large (100m perhaps) you will inevitably run out of stack.
- nineteen999 5y agoAs much as I love recursive algorithms, I couldn't agree with you more. Why do the clever and pretty thing, when it is better to do the less elegant but reliable thing.
- omegalulw 5y ago+1, though in general designing an iterative solution is more effort for problems that have intuitive recursive solution so OPs argument has some merit.
- atq2119 5y agoI agree where there isn't inherently a stack. Many of the introductory examples of recursion are trivially transformed to an iteration in constant space. However, there are plenty of interesting cases where if you don't use recursion, you end up having to implement your own stack as a resizable vector. The question "why should the busy work of hand-rolling your own stack be necessary?" is the kind of question that you don't want to waste too much time on as a working programmer, but unless some people think deeply about such questions, the field as a whole stops progressing. As others point out in this discussion, with a 64-bit address space one could organize the stack(s) in such a way that recursion could use all of physical memory if necessary.
- deleted 5y ago[deleted]