Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order:
- reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken.
- space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others.
- time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker.
> Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.
I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution.
EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.
My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use recursion, otherwise use iteration (unless recursion with TCO is the native idiom of course).
I've never had an issue that wasn't an obvious bug that iteration would have somehow solved. If any bug that terminated a thread was fatal to the whole process then I suggest the thread termination handler should handle this more gracefully.
Increased space usage is a non-issue IMO. Translating a stack frame to a data structure you manage as an explicit stack requires the same space within a small constant factor.
And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
Quite likely :)
> And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
This is a very good point.
Alright, you've convinced me to start playing with recursion again. Just not in java or python.
So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context.
Best of luck, =)
An easy way to do it is to just pass a separate "depth" integer parameter into the recursive function. It then passes that +1 when it makes a recursive call. At the top of the function, if the depth is above your chosen limit, you bail out in some way instead of continuing to recurse.
> you detect that situation and make it work.
If you really do need to "make it work" for arbitrarily-deeply nested inputs, then you are actually better off using a heap-allocated stack instead of recursion.
But in most cases, a recursive implementation will only exceed the stack if the input is malicious or pathological and you can just fail in that case.
I didn't actually say that, but even supposing I meant that, walking a 3D mesh in a way that requires you to keep stack context sounds like a pretty unlikely/niche scenario, so it seems even that stronger statement is true.
It's fairly intuitive to walk a mesh recursively by following adjacent edges and you have to keep track of where you've been which means storing a lot of data somewhere. Maybe there are better algorithms but sometimes you just reach for what's most obvious. I suppose there are many analogous applications of traversing a graph structure.
Of course you can, if you wanted to, just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue.
Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.