On 4/28/2012 1:33, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> That said, I've found I rarely need it
>
>    It's not usual to need it, but sometimes it can be quite useful.
> Almost anything involving things like permutations and combinations
> are significantly easier to express recursively than iteratively.

Fair enough. That said, you can usually tell by looking at the input 
structure how deeply you'll likely need to recurse for something like that.

>> If you can handle the program crashing when you
>> give it too much data in a way that generates bogus results, then sure, feel
>> free. :-)
>
>    As I said, if the recursion depth is O(log n), then you *can't* give it
> so much data as for the stack space to run out. It's physically impossible.

Oh? How deep is your stack? Are you sure your on-the-heap data structure 
hasn't used up all your potential stack space?

The point is not that if the algorithm is all you're doing, you won't run 
out of stack space. The point is that you don't know how much stack depth 
you have, what's on the stack above you, or how big your data structure is, 
even assuming you're recursing due to a data structure.

Or how much stack space the thing you're calling during the recursion takes, 
if your recursion is part of a more generic data structure. If you say 
"process each node of the DOM with this lambda", you don't know what that 
lambda is going to do.

Why does C++ limit the depth of template instantiation required to 17 
levels, or whatever it is? Clearly, it's possible to run out of stack doing 
recursion.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message