Recursion problem

[hpfreak080]

I have to make a recursive function that is passed a location in a previously allocated 2D array, and changes the "color" (indicated by a letter) from the "oldColor" to the "newColor." The function then changes any adjacent elements containing the "oldColor" to the "newColor." (If you are confused by this just let me know. It took my professor 3 pages to explain the color grid to us lol).

Here is what I have.:

void Color_Grid::paintRegion(int row, int col, char oldColor, char newColor){
	//make sure everything stays in bounds
	if(row < 0 || row >= rows){ return; }//go back if out of bounds because there is nothing to change anyway
	if(col < 0 || col >= cols){ return; }//go back if out of bounds because there is nothing to change anyway

		//Base Cases
	if(grid[row][col] != oldColor){ return; }//if the character is not the old color, there is nothing to do
	
	//if the character IS the old color, change it to the new color
		grid[row][col] = newColor;
		return;//POSSIBLE PROBLEM RETURN STATEMENT!!

	//Check up, down, left, and right from current location
		paintRegion(row-1,col,oldColor,newColor);//Check above location
		paintRegion(row+1,col,oldColor,newColor);//Check below location
		paintRegion(row,col-1,oldColor,newColor);//Check left of location
		paintRegion(row,col+1,oldColor,newColor);//Check right of location
}

I believe the problem lies in the return statement I have indicated in my code above causing the function to return back to main after the first call without calling its self. I've moved everything around though and any other arrangement causes the program to crash. Any help would be appreciated!

[firedraco]

Yes, that is the issue. However, you also have another issue, since if you call it from location (x,y), it will call it on location (x-1,y), which will then call it on location (x,y) again, causing an infinite loop. If you want to do this using recursion (I would not suggest that, I would just use nested for loops), then pass the width and the height as parameters, and only recurse in one direction (from 0,0 -> 0,y_max), then increment x, and repeat. Like I said though, using recursion here would simply waste stack space and cause issues like what you are having.

[hpfreak080]

unfortunately, I have to use recursion (part of the assignment). If I had been allowed to do this my way I would have used for loops already lol.

the width and height of the 2D array are data members (the variables "rows" and "cols").

[hpfreak080]

haha well, for some reason moving my return statement after all of the recursions seemed to work (I could have sworn I tried that before) even though I though it would crash on me. I know that I was getting an infinite loop before (I tested it with some cout statements) but thanks for your help firedraco, you got me thinking for sure.

[helios]

In case you're interested in know how this algorithm is done properly:
http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations

[hpfreak080]

thanks helios.

I don't think I would've used recursion if I had had more freedom to do this assignment mostly because I can wrap my mind around loops (even nested) much easier than recursion.