Darren New <dne### [at] sanrrcom> wrote:
> >    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?

  As I said, if your recursion depth is O(log n), then you would need a
ridiculous amount of data in order to run out of stack space even with
a very stack-hungry recursive function. (For example, if your recursion
level were 50, then the input data, even if it took just 1 byte per element,
would require something like 1024 terabytes of RAM. How likely are you going
to run out of stack space with that few recursion levels? You could easily
have that many function calls on the stack even without recursion.)

  It's highly unusual to require enormous amounts of stack on one single
function call, especially if you are implementing a recursive algorithm.
If each function call takes exponentially more stack space than there's
input, you are doing something wrong. (And even if you did, your algorithm
would be quite slow, as each function call would be operating on a rather
large amount of local data.)

> Why does C++ limit the depth of template instantiation required to 17 
> levels, or whatever it is?

  Never heard of such a limit.

-- 
                                                          - Warp

Post a reply to this message