You'd sure need a pretty tiny stack and/or an unbelievable amount of context on stack to worry too much about this.
If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements.
This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization.
I'm not a huge fan of recursion, but let's not resort to too much hyperbole in our arguments against it. :P
> If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements.
This is incorrect.
Your limit is only for fully balanced trees. On a fully unbalanced tree your solution will crash at about 100 elements.
Do we see a lot of unbalanced trees? Yes, most of the time in my experience. If there's a balanced tree, there's probably a data structure and the function is already supplied. Writing a tree traversal function come up when working with unbalanced things like program ASTs, JSON/HTML/XML parsed data, Lisp-style lists, filesystem traversal, etc.
> This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization.
The compiler cannot elide away tree traversal with tail-call optimisation. Only one branch.
A really smart compiler could transform it into a loop with an explicit node-stack using an array, or avoid the stack and use in-place pointer-reversal if concurrency rules permit and there's a spare bit. But I've never seem a really smart compiler do either of those things.
> Your limit is only for fully balanced trees. On a fully unbalanced tree your solution will crash at about 100 elements.
5E29 assumes not-quite-balanced. Yes, I'm assuming some kind of balanced binary tree data structure, not other things that are tree-like. There are some things that are much better than 5E29, like btrees. :P
If you have really deep unbalanced trees, you may want to have a smaller stack frame and/or pay the pain of doing things iteratively with your own stack. (Or have upward links in your tree and do it purely iteratively but slow).
> The compiler cannot elide away tree traversal with tail-call optimisation. Only one branch.
Yah, sorry. Just for search, not for full traversal.
I have 20KB total RAM on the MCU I'm currently programming for. It's not too hyperbolic to imagine real-world cases where some recursive functions would be unsuitable.
They're handy for some parsing and scripting scenarios however, I'll grant you that.
Probably you were limited to a single 64k segment for stack... still would have required a really big amount of context per call to blow stack so quickly.
Back in the mid 80's on DOS I had no problem recursing 30+ levels deep.
Hmm, let's see. The last time I blew the computer's stack due to tree recursion was in 1995 (it was six levels deep). Since then, I've never seen a stack overflow due to tree recursion (presumably because none of the trees I've operated on were deeper than the hardware stack, and I switched from C to Python where the stack is far, far deeper).
If I were writing a server that needed better memory requirements, I could certainly transform my code if desired.
If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements.
This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization.
I'm not a huge fan of recursion, but let's not resort to too much hyperbole in our arguments against it. :P