Jump to content
  • Advertisement
Sign in to follow this  
Ezbez

Problem with recursion with c++

This topic is 4886 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've just started using recursion in one of my functions. It was working pretty well, until I started to get strange fatal crashes. I happened to stumble across a tutorial online that said that a recursive function can sometimes crash the program if it loops for too long. I'm thinking that this is what is happening in my game, though I'm not 100% sure. First off, is there any easy, simple way to figure out if its recursion that is crashing it? Secondly, if it is recursion, then how can I fix that? I've already tried a pretty obvious method of calling functionB() in functionA() where functionB simply calls another functionA, but that did not work. Another quick question, how can I access the data members of an object that I only hve a pointer to? So far, all I've done is used a function that gets the data members. I'm doubting that the code to the function would help, but I can post it if it is necessary.

Share this post


Link to post
Share on other sites
Advertisement
Firstly I try to avoid using recursion, this is a personal opinion and not a fixed rule.

Anyway as for the pointer to an object; I presume you are using C++ if so:

object->member = 12;

This is also presuming the member is public

Share this post


Link to post
Share on other sites
If your program is crashing because it's recursing too deeply then it will normaly fail because of the stack overflowing.

The exception thrown will be 0xC00000FD (Stack Overflow).

If you debug the app it should show the exception being thrown - unless you've got a catch {..} in your code (if you have you can tell the debugger to show the exception anyway).

Here's an obvious program to create a stack overflow exception:


void afunc(long x, long y, long z) {
afunc(x,y,z);
}

int main(int argc, char* argv[])
{
afunc(1,2,3);
return 0;
}


Share this post


Link to post
Share on other sites
Hi,

I haven't heard of inherent "design" flaws of the recursive functions..
What might happen is to have way too many depth level and that amount of
stack memory eaten to impact performance, in unlikely events leading to crashes.

So, you should perhaps show us the source code of your function and we might
be able to spot some error in there.

About the data members. You should not access them at all, if you were to follow
the correct absolute design procedure of a class. You should use the appropriate
"get" / "put" methods in that class. If you are using data in that object and you
really really want to access it, just make it public and use p->mydata.. I am not
sure I understand what you mean by "Access" here.

Share this post


Link to post
Share on other sites
I also don't know why a recursive function should crash by itself if not due to stack overflow. However, notice that not the recursion depth by itself may be the problem, but the product of recursion depth and stack space allocation per recursion. I.e. heavy allocation of local variables per invocation lets the stack overflow occur at a relatively shallow recursion depth. That counts for overhanded variables also, since they are pushed (most often) as local copies onto the stack.

Share this post


Link to post
Share on other sites
Without seeing the source code, I'ts hard to tell what the problem is. That being said, every recursive function should have an exiting condition (otherwise you would recurse until you run out of stack space). Assuming that the problem is stack overflow, I would check this condition and check any suspicious places in the rest of your code that might be tripping this up. Good luck.

Share this post


Link to post
Share on other sites
Unless you have a heavy resource allocation or a very large problem size, stack overflow from recursion usually results from the recursions being 'infinite' (unbounded) - this will be due to a coding error that prevents the recursion from stopping. That is, the function has to be designed in such a way that it does not call itself *every* time, and actually such that for any input, it will eventually stop calling itself. Typically this is accomplished by arranging that one of the parameters is always decreased towards 0 (or some other value) for the recursive call, and checking for that value and not recursing when it is reached. Usually this parameter is natural (e.g. for merge sort, it is the length of the current list being sorted, and we can handle a list of 0 or 1 items by simply returning the unmodified list), but sometimes it must be artificial (e.g. if you are drawing a recursively-defined fractal).

Given a pointer to an object, you can dereference it to get "the object" in the same way that you would dereference a pointer to an int or anything else. Given that, you can then access its data members normally. So conceptually you would like (*myObject).member. This works, but C++ also provides a clearer (and generally preferred syntax): myObject->member. This allows for easy handling of the case where the member is in turn a pointer to some other object that you want to look at, etc. foo->bar->baz->quux is a lot easier to get right than (*(*(*foo).bar).baz).quux :)

Share this post


Link to post
Share on other sites
Well, my function should *not* be repeating forever. However, it doesn't exactly have any specific condition to not repeat, but it does have strict requirments to call itself.

As for high demands, it only uses three integers.

Heres the source(its a little big, and quite messy)

A breif description of what it does. This raises one corner on a tile then figures out all the other corners that have to be raised. Sometimes it can create a cascading effect of raising tiles that each need to raise other tiles.


void World::subRaiseTile(int num,int corner)
{
int index=0;
if(num<0||num>=10000){return;}
index = tileMap[num]->raiseCorner(corner);/*Okay, this needs a little explanation. Basically, it calls another function that does the real work behind this. That returns either 1,4,5,6, or 7 which is stored in index.*/


if(index==4)
{
if((*tileMap[num]).ce!=1)
{
tileMap[num]->CE(1);
if(num-98>0){subRaiseTile(num-98,3);}
if(num-99>0){subRaiseTile(num-99,2);}
if(num+1<10000){subRaiseTile(num+1,0);}
}

if((*tileMap[num]).cw!=1)
{
tileMap[num]->CW(1);
if(num+98<10000){subRaiseTile(num+98,1);}
if(num+99<10000){subRaiseTile(num+99,0);}
if(num-1>0){subRaiseTile(num-1,2);}
}
}

if(index==5)
{
if((*tileMap[num]).cn!=1)
{
tileMap[num]->CN(1);
if(num-100>0){subRaiseTile(num-100,2);}
if(num-99>0){subRaiseTile(num-99,3);}
if(num-1>0){subRaiseTile(num-1,1);}
}

if((*tileMap[num]).cs!=1)
{
tileMap[num]->CS(1);
if(num+100<10000){subRaiseTile(num+100,0);}
if(num+99<10000){subRaiseTile(num+99,1);}
if(num+1<10000){subRaiseTile(num+1,3);}
}
}

if(index==6)
{
if((*tileMap[num]).ce!=1)
{
tileMap[num]->CE(1);
if(num-98>0){subRaiseTile(num-98,3);}
if(num-99>0){subRaiseTile(num-99,2);}
if(num+1<10000){subRaiseTile(num+1,0);}
}

if((*tileMap[num]).cw!=1)
{
tileMap[num]->CW(1);
if(num+98<10000){subRaiseTile(num+98,1);}
if(num+99<10000){subRaiseTile(num+99,0);}
if(num-1>0){subRaiseTile(num-1,2);}
}
}
if(index==7)
{
if((*tileMap[num]).cs!=1)
{
tileMap[num]->CS(1);
if(num+100<10000){subRaiseTile(num+100,0);}
if(num+99<10000){subRaiseTile(num+99,1);}
if(num+1<10000){subRaiseTile(num+1,3);}
}

if((*tileMap[num]).cn!=1)
{
tileMap[num]->CN(1);
if(num-100>0){subRaiseTile(num-100,2);}
if(num-99>0){subRaiseTile(num-99,3);}
if(num-1>0){subRaiseTile(num-1,1);}
}
}

if(index==1)
{
/*North*/
if(tileMap[num-98]->cw > tileMap[num-98]->height - tileMap[num]->height)
{
if(num-100>0){subRaiseTile(num-100,2);}
if(num-99>0){subRaiseTile(num-99,3);}
if(num-1>0){subRaiseTile(num-1,1);}
}

/*East*/
if(tileMap[num-98]->cw > tileMap[num-98]->height - tileMap[num]->height)
{
if(num-98>0){subRaiseTile(num-98,3);}
if(num-99>0){subRaiseTile(num-99,2);}
if(num+1<10000){subRaiseTile(num+1,0);}
}


/*South*/
if(tileMap[num+99]->ce > tileMap[num+99]->height - tileMap[num]->height)
{
if(num+100<10000){subRaiseTile(num+100,0);}
if(num+99<10000){subRaiseTile(num+99,1);}
if(num+1<10000){subRaiseTile(num+1,3);}
}

/*West*/
if(tileMap[num+98]->ce > tileMap[num+98]->height - tileMap[num]->height)
{
if(num+98<10000){subRaiseTile(num+98,1);}
if(num+99<10000){subRaiseTile(num+99,0);}
if(num-1>0){subRaiseTile(num-1,2);}
}
}
}




I doubt that that will be enough information to do it with, but prehaps it will be. Oh, the mysterious tileMap[] has 10000 'tiles' in it. Hence the check at the begining for whether or not its in that range.

The error message that I get is actually a segmentation fault at the first if test when doing the stuff for when index ==1. All the errors seem to occur when index equals one.

Thanks for the help with the pointers, that works now.

Share this post


Link to post
Share on other sites
Sometimes you call it with a smaller num sometimes with a bigger num, are you sure that this doesn't loop? Like 1,2,3,4,...,98,99,1,2,3,4,...,98,99,...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!