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
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.
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.
They're handy for some parsing and scripting scenarios however, I'll grant you that.
Back in the mid 80's on DOS I had no problem recursing 30+ levels deep.
If I were writing a server that needed better memory requirements, I could certainly transform my code if desired.
