stack overflow

Discussion in 'C++' started by Allen, Nov 16, 2003.

  1. Allen

    Allen Guest

    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
     
    Allen, Nov 16, 2003
    #1
    1. Advertising

  2. Allen

    Allen Guest

    > 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
     
    Allen, Nov 17, 2003
    #2
    1. Advertising

  3. "Allen" <allen-terri-ng!@#att.net> wrote in message
    news:NnUtb.271894$...
    > > 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
     
    Tanguy Fautré, Nov 17, 2003
    #3
  4. >
    > "Allen" <allen-terri-ng!@#att.net> wrote in message
    > news:NnUtb.271894$...
    > > > 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...)
     
    Tanguy Fautré, Nov 17, 2003
    #4
  5. 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.
     
    Gianni Mariani, Nov 17, 2003
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?amJpeEBuZXdzZ3JvdXBzLm5vc3BhbQ==?=

    Stack overflow exception

    =?Utf-8?B?amJpeEBuZXdzZ3JvdXBzLm5vc3BhbQ==?=, Apr 20, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    7,296
    Rick Spiewak
    Apr 22, 2004
  2. Mr m?ll
    Replies:
    2
    Views:
    1,424
    Mr m?ll
    Oct 16, 2004
  3. Replies:
    0
    Views:
    521
  4. Replies:
    0
    Views:
    416
  5. Kenneth McDonald

    Why stack overflow with such a small stack?

    Kenneth McDonald, Aug 30, 2007, in forum: Ruby
    Replies:
    7
    Views:
    290
    Kenneth McDonald
    Sep 1, 2007
Loading...

Share This Page