Blob ...how to write non-recursively

Question

I have written the following program, using recursion, but I can't figure out how to write it non-recursively. Every time I run my non-recursive version the numbers are way off. Any suggestions on how to write the following method without recursion?

int countCells(color grid[ROWS][COLS], int r, int c) {
 if (r < 0 || r >= ROWS || c < 0 || c >= COLS) {
   return 0;
 } else if (grid[r][c] != ABNORMAL) {
   return 0;
 } else {
   grid[r][c] = TEMPORARY;
   return 1
     + countCells(grid,r-1,c-1) + countCells(grid,r-1,c)
     + countCells(grid,r-1,c+1) + countCells(grid,r,c+1)
     + countCells(grid,r+1,c+1) + countCells(grid,r+1,c)
     + countCells(grid,r+1,c-1) + countCells(grid,r,c-1);
    }
}

This is what I have tried btw:

int countCells(color grid[ROWS][COLS], int r, int c)
{
  int temp = 0;
  if (r < 0 || r >= ROWS || c < 0 || c >= COLS)
  {
    return 0;
  }

  else if (grid[r][c] != ABNORMAL)
  {
    return 0;
  }

  else
  {
    int original_row = r;
    int original_column = c;

    while(r >= 0 && row < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r - 1;
      c = c - 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r - 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r - 1;
      c = c + 1;
     }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      c = c + 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r + 1;
      c = c + 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r + 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r + 1;
      c = c - 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      c = c - 1;
    }
    r = original_r;
    c = original_c;

    return temp;
  }
}

Answer 1

int count = 0;
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < COLS; j++) 
    {
        if (grid[i,j] != ABNORMAL) count++;
    }
}

Answer 2

The easiest way to do this non-recursively is to maintain a list of places to check. Pseudocode would look like this:

list horizon = new empty list;
horizon.push(r, c);
count = 0;
while(!horizon.empty())
{
   r, c = horizon.pop();
   if(boundscheck(r, c) && grid[r][c] == ABNORMAL)
   {
        count++;
        horizon.push(r-1, c-1);
        horizon.push(r-1, c  );
        // etc ...
        grid[r][c] = TEMPORARY;
   }
}

EDIT: You should definitely look at this post on flood fill algorithms.

Answer 3

This appears to be a classic flood fill algorithm. A non-recursive flood fill routine is a bit tricky to write; you will need temporary storage somewhere, and the stack is the easiest place to get it. The linked article discusses some other techniques, including using the array itself as temporary space (the right-hand fill algorithm).