By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,261 Members | 1,325 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,261 IT Pros & Developers. It's quick & easy.

stack overflow

P: n/a
Hi all,

What are some different approaches to dealing with stack overflows in
C++? I'm especially interested in approaches concerned with speed for
infrequent overflows.
--

Best wishes,
Allen


Jul 19 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
> What are some different approaches to dealing with stack overflows in
C++? I'm especially interested in approaches concerned with speed for
infrequent overflows.

Even more specifically, I have a recursive BST function for a
potentially very large tree. What kinds of schemes have others come up with
for dealing with stack overruns of this type?
--

Best wishes,
Allen


Jul 19 '05 #2

P: n/a

"Allen" <allen-terri-ng!@#att.net> wrote in message
news:Nn***********************@bgtnsc04-news.ops.worldnet.att.net...
What are some different approaches to dealing with stack overflows in C++? I'm especially interested in approaches concerned with speed for
infrequent overflows. Even more specifically, I have a recursive BST function for a
potentially very large tree. What kinds of schemes have others come up

with for dealing with stack overruns of this type?
--

Best wishes,
Allen


You can optimize the recursive function to use up less stack, for example by
using global (or member) variables instead of local variables.

See if you really need the recursivity. For example, IIRC a search in a BST
tree doesn't require a recursive function scheme but can work simply within
a loop.

There are other ways to optimize recursive functions.
But sometimes if there is really no solution then you have to make your own
stack and de-recursive the whole thing. But think of it as a last ressort,
and it's a very rare situation.

But I still think that for a BST there is no need for recursivity at all in
most, if not all, cases.

Yours,

Tanguy
Jul 19 '05 #3

P: n/a
>
"Allen" <allen-terri-ng!@#att.net> wrote in message
news:Nn***********************@bgtnsc04-news.ops.worldnet.att.net...
What are some different approaches to dealing with stack overflows in C++? I'm especially interested in approaches concerned with speed for
infrequent overflows. Even more specifically, I have a recursive BST function for a
potentially very large tree. What kinds of schemes have others come up

with
for dealing with stack overruns of this type?
--

Best wishes,
Allen


You can optimize the recursive function to use up less stack, for example

by using global (or member) variables instead of local variables.

See if you really need the recursivity. For example, IIRC a search in a BST tree doesn't require a recursive function scheme but can work simply within a loop.

There are other ways to optimize recursive functions.
But sometimes if there is really no solution then you have to make your own stack and de-recursive the whole thing. But think of it as a last ressort,
and it's a very rare situation.

But I still think that for a BST there is no need for recursivity at all in most, if not all, cases.

Yours,

Tanguy


Well there are cases where you cannot easily avoid recursivity, like a
prefix run through the tree (or any other depthfirst run), but then if you
have a stack overflow with a well written recursive function it means your
tree is unbalanced and then I suggest you look up for another structure but
similar such as a red-black tree (which is by the way the most common
implementation of std::map, so...)
Jul 19 '05 #4

P: n/a
Allen wrote:
What are some different approaches to dealing with stack overflows in
C++? I'm especially interested in approaches concerned with speed for
infrequent overflows.


Even more specifically, I have a recursive BST function for a
potentially very large tree. What kinds of schemes have others come up with
for dealing with stack overruns of this type?

Have you tried to allocate a bigger stack ? Some OS's allow you to
create bigger stacks.

Another alternative is to not use a recursive call but to create an
object that allows you to "stack" state in a "frame" object.
e.g.

// recursive function

int Recursive( node * here )
{

int has_stuff = 0;

if ( here )
{
has_stuff = here->do_some_stuff();

has_stuff += Recursive( here->left );

has_stuff += Recursive( here->right );

}

return has_stuff;
}

//
// non-recursive way to do the same thing -
//

//
// This class stores the state that would have been stored
// on the stack.
//

class Stuffer
{
public:

int m_has_stuff;
node * m_node;

enum State
{
DoLeft,
DoRight,
Done
};

State m_state;

Stuffer( node * i_here )
: m_has_stuff( i_here->do_some_stuff() ),
m_here( i_here ),
m_state( DoLeft )
{}

void Next()
{
switch ( m_state )
case DoLeft : m_state = DoRight; break;
case DoRight : m_state = Done; break;
case Done : break;
}
}
};

//
// This method performs everything in a while loop - no
// recursive calls.
//

int NonRecursive(node * here)
{

std::list<Stuffer> stuff_stack;

stuff_stack->push_front( Stuffer( here ) );

while ( stuff_stack->begin() != stuff_stack->end() )
{
std::list<Stuffer>::iterator p_stuffer = stuff_stack->begin();

switch ( p_stuffer->m_state )
{
case DoLeft :
stuff_stack->push_front(Stuffer(here->left));
p_stuffer->Next();
break;
case DoRight :
stuff_stack->push_front(Stuffer(here->right));
p_stuffer->Next();
break;
case Done :
std::list<Stuffer>::iterator p_last = p_stuffer;
p_last ++;
if ( p_last == stuff_stack->end() )
{
return p_stuffer->m_has_stuff;
}
p_last->m_has_stuff += p_stuffer->m_has_stuff;
stuff_stack->erase( p_stuffer );
break;
}
}

// should never get here
return 0;
}
..... this is all off the top of my brain - I didn't compile or verify
that this works - I just thought it's a good example of how to decompose
a recursive function into a separate stack.

Jul 19 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.