🔒 Locked

Help with Recursion

Started by kcolc_22 Apr 22, 2001 at 3:10 PM 4 replies 350+ views

Original Post

Apr 22, 2001 at 3:10 PM

I need to implement a recursive function to compute the number of 0 that are next to another 0. A data file is read into an array, and looks something like this: 111111111111111 100110011010001 110010000011101 111011110001101 111000111011111 111001100000111 111111111111111 This is the section where i''m think the recursion need to go? void AreaCal() { if ((Grid[Row][Col] == ''1'') || (Grid[Row][Col] == ''²'')) Area = 0; else { Grid[Row][Col] = ''²''; Area ++; } } This section takes the coordinates entered in by user and check to see if the coordinates contains a 0 or 1. If it contains a 0 then it replace the 0 with ASCII value 178. I have an ideal on how to implement the recursion, just not sure how to code it out to make it work. Any suggestion?

jaxson

Apr 23, 2001 at 11:20 PM

Try something similar to this:

  
int AreaCal(int row, int col)
{
  // make sure we are in bounds of array

  if(row >= MAX_ROW || row < 0)
     return 0;
  if(col >= MAX_COL || col < 0)
     return 0;

  if(grid[row][col] == ''1'' || grid[row][col] == ''2'')
     return 0;

  // else, we have a ''0''

  grid[row][col] = ''2''; // mark off the spot as counted


  // return this space (1) plus the number of 0''s in all

  // directions

  return 1 + AreaCal(row-1, col) + AreaCal(row+1, col) + 
      AreaCal(row, col-1) + AreaCal(row, col+1);


}

This should hopefully, work, but might have a bug or two. You need to remember with recursion to always have a terminating case (in this situation, it is if you are out of bounds of the array or on a non-''0'' space).

Be sure to let me know what grade I get on this assignment.

djsteffey

Apr 23, 2001 at 11:42 PM

that looks too much like a homework problem to me.
b/c i remember doing something similar when i was in my first semester of c++

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."
- Mr. T

kcolc_22

Apr 24, 2001 at 6:28 PM

quote:
Original post by jaxson

Try something similar to this:

    
int AreaCal(int row, int col)
{
  // make sure we are in bounds of array

  if(row >= MAX_ROW || row < 0)
     return 0;
  if(col >= MAX_COL || col < 0)
     return 0;

  if(grid[row][col] == ''1'' || grid[row][col] == ''2'')
     return 0;

  // else, we have a ''0''

  grid[row][col] = ''2''; // mark off the spot as counted


  // return this space (1) plus the number of 0''s in all

  // directions

  return 1 + AreaCal(row-1, col) + AreaCal(row+1, col) + 
      AreaCal(row, col-1) + AreaCal(row, col+1);


}

Thanks Jaxson for you input, got me through coder''s block. lol

   
unsigned AreaCal(unsigned X,unsigned Y)
{
  if ((Grid[X][Y] == ''1'') || (Grid[X][Y] == ''²''))
    Area = 0;
  else
  {
    Grid[X][Y] = ''²'';
    Area ++;
    return AreaCal(X-1,Y)+AreaCal(X+1,Y)+
	   AreaCal(X,Y-1)+AreaCal(X,Y+1);
  }
}

Now I just have to debug one little bug. Thanks for your help

kcolc_22

Apr 24, 2001 at 6:28 PM

quote:
Original post by jaxson

Try something similar to this:

    
int AreaCal(int row, int col)
{
  // make sure we are in bounds of array

  if(row >= MAX_ROW || row < 0)
     return 0;
  if(col >= MAX_COL || col < 0)
     return 0;

  if(grid[row][col] == ''1'' || grid[row][col] == ''2'')
     return 0;

  // else, we have a ''0''

  grid[row][col] = ''2''; // mark off the spot as counted


  // return this space (1) plus the number of 0''s in all

  // directions

  return 1 + AreaCal(row-1, col) + AreaCal(row+1, col) + 
      AreaCal(row, col-1) + AreaCal(row, col+1);


}

Thanks Jaxson for you input, got me through coder''s block. lol

   
unsigned AreaCal(unsigned X,unsigned Y)
{
  if ((Grid[X][Y] == ''1'') || (Grid[X][Y] == ''²''))
    Area = 0;
  else
  {
    Grid[X][Y] = ''²'';
    Area ++;
    
  }
  return AreaCal(X-1,Y)+AreaCal(X+1,Y)+
	   AreaCal(X,Y-1)+AreaCal(X,Y+1);
}

Now I just have to debug one little bug. Thanks for your help

kcolc_22

Apr 24, 2001 at 6:39 PM

Sorry for the double posting.. just messed up on writing the first msg.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.