• ### Popular Now

• 12
• 12
• 9
• 10
• 13

#### Archived

This topic is now archived and is closed to further replies.

# Are recursive functions limited? Yes.

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

## Recommended Posts

I've created a realistic height map for my game, and then added water to it. The water travels from a single point to everything around it as far as it can travel while the land is lower than the water level. I have a single function that checks 4 points around its single point, and calls itself if that direction's land and water levels are below its own point. Since my map's width * height = 307200, is this too much for recursive functions to handle? My program crashes while trying to access a pointer, yet the pointer's address is still within range right before it accesses it. I'm completely clueless as to why it's happening. I'm passing 4 arguments to the function itself, and have plenty enough memory for them, even if there was one function per point. Anyway, this is the function. "Mw" and "Mh" are the Width and Height of the map, and "Mp" and "Wt" are pointers to LandHeight and WaterLevels. And there are 8 defines that move the pointers:
#define KLH (*(Mp-1))
#define KRH (*(Mp+1))
#define KTH (*(Mp-Mw))
#define KBH (*(Mp+Mw))
#define KOH (*Mp)

#define KLW (*(Wt-1))
#define KRW (*(Wt+1))
#define KTW (*(Wt-Mw))
#define KBW (*(Wt+Mw))
#define KOW (*Wt)

VOID KTileWaterScan(LONG x,LONG z,USHORT *Mp,USHORT *Wt)
{
KOW = WaterLevel;

if(x > 0)
if(KOW > KLH && KOW > KLW)
KTileWaterScan(x-1,z,Mp-1,Wt-1);
if(x < Mw-1)
if(KOW > KRH && KOW > KRW)
KTileWaterScan(x+1,z,Mp+1,Wt+1);
if(z > 0)
if(KOW > KTH && KOW > KTW)
KTileWaterScan(x,z-1,Mp-Mw,Wt-Mw);
if(z < Mh-1)
if(KOW > KBH && KOW > KBW)
KTileWaterScan(x,z+1,Mp+Mw,Wt+Mw);
}   
This routine is only used in my world editor, so I'm not worrying about much except speed and accuracy. Thanks for any clues. And I would also appreciate any other alternative ideas to this. I was scanning the entire map over and over until nothing changed, but it took a full 15 seconds just to finish. -Jiia "1 and 1 is 1 11" - tool [edited by - Jiia on September 12, 2002 10:34:05 AM]

##### Share on other sites
You are probably mashing your stack if you compiler doesnt support tail optimisation (many dont). Solve it iteratively (ie with a for/while loop).

##### Share on other sites
The for/while loop is how the routine worked before this routine. But it is extremely slow.

What about allocating memory for each recursion? Would it help if I allocated an object with new for each direction to hold the parameters, and made the function a member of that object so that no paremeters are needed?

[edited by - Jiia on September 12, 2002 9:38:19 AM]

##### Share on other sites
Even if the compiler supports tail optimization, this code wouldn''t trigger it. The thread of control is heading down two recursive function calls, so it''s going to be growing the stack to matter what.

Using new in the manner you describe won''t help, Jiia. You need to recode this as an iterative solution. This is not a good problem to solve recursively!

Also, recursive algorithms are generally _not_ faster than an iterative one. If you can''t write a fast iterative version, you''re not going to have much luck with a recursive version.

##### Share on other sites
Recursion isn''t going to be any faster than a well-implemented iterative solution. Once you start storing data on the heap rather than the stack you may as well go the whole way and do it iteratively anyway.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

##### Share on other sites
quote:
Original post by Anonymous Poster
Even if the compiler supports tail optimization, this code wouldn''t trigger it. The thread of control is heading down two recursive function calls, so it''s going to be growing the stack to matter what.

I never knew that. Thanks.

##### Share on other sites
Well, you're right, I still get a crash using new. I don't understand why, though. I'm not using the stack at all, am I? This is very messy, but take a look, the only place the stack is being used is in the constructor, right?..
struct KWaterScan{	LONG x,z;	USHORT *Mp,*Wt;	KWaterScan(LONG cx,LONG cz,USHORT *mp,USHORT *wt) { x=cx; z=cz; Mp=mp; Wt=wt; }	VOID DoScan()	{		KOW = ScanValue;		if(x > 0)			if(KOW > KLH && KOW > KLW)				(new KWaterScan(x-1,z,Mp-1,Wt-1))->DoScan();		if(x < Mw-1)			if(KOW > KRH && KOW > KRW)				(new KWaterScan(x+1,z,Mp+1,Wt+1))->DoScan();		if(z > 0)			if(KOW > KTH && KOW > KTW)				(new KWaterScan(x,z-1,Mp-Mw,Wt-Mw))->DoScan();		if(z < Mh-1)			if(KOW > KBH && KOW > KBW)				(new KWaterScan(x,z+1,Mp+Mw,Wt+Mw))->DoScan();		delete this;	}};
This code (as well as the top code) work perfectly unless the area is very large. By the way, using new in this manner is very fast. At least compared to my old loops. Does anyone have any ideas about a good way to iteratively solve this? The only way I know of is my old path finding routine, where I used a min and max distance (from start) and scanned (over and over mind you) the points between min and max in a square shape manner, growing max to the outer most changed point, and keeping min at the inner most changed point. That method was hideous to code, though.

I would greatly appreciate any suggestions..

BTW, what about something like Directory parsing? Would that be a bad place to use recursive functions as well? Where each recursion is made for a new directory? Just curious.

Thanks for the replies.

[edited by - Jiia on September 12, 2002 10:12:08 AM]

##### Share on other sites
quote:
Original post by Jiia
Well, you''re right, I still get a crash using new. I don''t understand why, though. I''m not using the stack at all, am I? This is very messy, but take a look, the only place the stack is being used is in the constructor, right

When you make a function call, besides parameter passing, the compiler does a stack push of the current instruction as well. This is later used to return to the proper place at the end of function execution.

So, if you do too many function calls (even with no parameters!) you fill up your stack with these return locations.

##### Share on other sites
Oh I see. So I''m screwed with this approach. Guess it''s back to the meditation room for me. Thanks for all of the help.