473,320 Members | 1,719 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

stack overflow

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
4 6668
> 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

"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
>
"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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: ip4ram | last post by:
I am quite puzzled by the stack overflow which I am encountering.Here is the pseudocode //define stack structure //function operating on stack void my_stack_function( function parameters) {...
7
by: Aguilar, James | last post by:
Hello all, To begin, yes, this -is- a homework assignment. However, it is for my Algorithms class, and my instructor has given us explicit permission to use "expert" groups like newsgroups, so...
19
by: Jim | last post by:
I have spent the past few weeks designing a database for my company. The problem is I have started running into what I believe are stack overflow problems. There are two tab controls on the form...
4
by: Victor | last post by:
Hello, I've got a situation in which the number of (valid) recursive calls I make will cause stack overflow. I can use getrlimit (and setrlimit) to test (and set) my current stack size. ...
2
by: David W. Walker | last post by:
I am attempting to port a C code that runs OK on a number of Linux and Unix machines to Windows XP using Visual Studio C++. I have set the program up as a console application, but when I try to run...
2
by: Ali | last post by:
Hi, I got stack overflow errors while using an unmanaged dll from managed c# application. When i use editbin.exe to increase stack size of app , it works. Is there a way to increase stack size of...
6
by: Daz | last post by:
Hi everyone! It is indeed, once again time for me to ask another stupid question. I have been searching around on the net for quite a while, and can't find anything that explains 'exactly'...
24
by: John | last post by:
I know this is a very fundamental question. I am still quite confused if the program call stack stack should always grows upwards from the bottom, or the opposite, or doesn't matter?? That means...
7
by: amit.atray | last post by:
Environement : Sun OS + gnu tools + sun studio (dbx etc) having some Old C-Code (ansi + KR Style) and code inspection shows some big size variable (auto) allocated (on stack) say for ex. char...
87
by: CJ | last post by:
Hello: We know that C programs are often vulnerable to buffer overflows which overwrite the stack. But my question is: Why does C insist on storing local variables on the stack in the first...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.