[mlyle]

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

[jlokier]

> 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.

[mlyle]

> 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.

[joefourier]

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.

[dekhn]

On my 1995 DOS-based computer, the C compiler I used at the time could handle roughly 6 levels deep.

[mlyle]

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.