For O(log n) worst case, as long as the constant factors weren't gigantic, I'd probably still use recursion. For example, I don't see a reason not to write introsort recursively.

Considering that your average recursive function with a stack growth of log(n) is likely to only overflow some point after the universe reaches maximum entropy, I wouldn't be too worried about it.
And this is only possible with algorithms implemented in a way where the upper bound isn't simply a function of the datatype size. (i.e. 2^32 or 2^64 max values for a comparison sort). Stack size is a compiler option you can control anyhow.

Considering that your average recursive function with a stack growth of log(n) is likely to only overflow some point after the universe reaches maximum entropy, I wouldn't be too worried about it.

QuickSort grows by n^2.

Unless specifically implemented so it doesn't.

You'd be surprised how many recursive algorithms can trivially blow the stack.

Fork/join, the fork part takes an array, then splits it into smaller pieces and hands those off to multiple cores. Algorithm grows by n. Library where I encountered this problem was written by someone who never tested with even moderately-sized array and didn't know about recursion problems. And it blew the stack, obviously only in production, when array had 10,000+ elements (which is tiny). Same problem as QS, but here partition sizes matter, so QS solution isn't directly possible.


Another problem is sufficiently smart compiler. Some compilers may choose to optimize tail recursion into a loop. Others might not. Result is that same code using different compiler/VM will blow stack, while other never will.

Python specifically does not perform such optimization for this very reason. It's one of most commonly requested features which won't be done.


Recursive behavior also carries other hidden cost, same as auto-allocation. If number of visited states is large, temporaries created on each step perform a lot of resource management. Not a problem with fib, but consider a DOM walker or UI toolkit, where kilobytes or even megabytes might be manipulated on each step. Solution here isn't necessarily removal of recursion, but moving resource management out of recursive path.

QuickSort grows by n^2.

I believe you meant O(n). If not, please explain where the n^2 comes from, because I am missing something.

[quote name='Antheus' timestamp='1328801553' post='4911332']
QuickSort grows by n^2.

I believe you meant O(n). If not, please explain where the n^2 comes from, because I am missing something.
[/quote]

Meh, n.

Reason it's worth mentioning is because most textbooks/references use naive partition which suffers from this problem. And despite "only" n, it doesn't take much to overflow the stack.