Public Group

# Count with recursion? C++

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

## Recommended Posts

This might seem simple to some people, but I've only used textbook examples of recursive functions. Brief description of what I'm trying to do. Same game that I asked about amorphous groups about, in fact same functions, but a different problem. The "flood fill" function that checks for the groups of objects seems perfectly fine (hasn't actually been tested however), but the next problem is counting how many objects are in each group. For now I think it really wouldn't cost much time (tens of milliseconds perhaps) with the current board size, but if it's ever increased, repeatedly going over the entire board with several functions could result in visible lag between the object falling and the popping animation. My question is, would it work to have a counter inside of a recursive function, before it calls itself, Or should I just make another function that simply goes over the board again, counting how many objects are in each group? Currently I have one function checkObjects() set a group number via recursive flood fill type function. Then I have a function countGroup() go over the entire board for each group just to count how many there are in each group. What also bothers me is that the countGroup() function is called within another function that loops until every group has been counted. In the end I have several hundred function calls just to set 2 values - the Group number and the boolean of whether it is to be popped when yet another function is called.

##### Share on other sites
Quote:
 Original post by SomeoneXMy question is, would it work to have a counter inside of a recursive function, before it calls itself, Or should I just make another function that simply goes over the board again, counting how many objects are in each group?

I reckon you can go either way, counting inside the recursion would be a bit faster. From the top of my head,

int gameGrid[h][w]; // The block data, 0 - no block, 1 - red, 2 - green, ...int visitedAreas[h][w]; // Initialized to 0 first to denote no positions checked yet./// Counts a single cell position and recurses to all others.void CheckPattern(int x, int y, int color, int &count){   if (visitedAreas[y][x] != 0)       return;   if (gameGrid[y][x] == color)   {      ++count;      visitedAreas[y][x] = color;      CheckPattern(x-1,y,color,count);      CheckPattern(x+1,y,color,count);      CheckPattern(x,y-1,color,count);      CheckPattern(x,y+1,color,count);   }}/// @return The number of blocks found of the same color starting from the given position.int CheckPattern(int x, int y){   int count = 0;   if (gameGrid[y][x] != 0)      CheckPattern(x, y, gameGrid[y][x], count);   return count;}/// Does a O(w*h) scan over the whole grid and performs game actions.void ScanGrid(){   Erase visitedAreas to 0.   for(int y = 0; y < height; ++y)      for(int x = 0; x < width; ++x)         if (visitedAreas[y][x] == 0)         {            int count = CheckPattern(x,y);            if (count >= 4)               Add (x,y) to To-Be-Exploded list;         }      Process To-Be-Exploded;}

Might have some bugs and/or syntax errors, just wrote it in the message reply box without testing. But the main idea - you can see how to carry that count variable as a reference inside the recursion. (You can do that without the reference, using a return value and passing a parameter as value, but I find this more readable)

##### Share on other sites
Wow, thanks.
Looks like I have some fixing to do ahead of me. Good thing I've been lazy and haven't done too much ;)

• 48
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631374
• Total Posts
2999654
×