stack overflow

[Allen]

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.

 

[Allen]

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?

 

[Tanguy Fautré]

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?

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

 

[Tanguy Fautré]

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...)

 

[Gianni Mariani]

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.