CODEWITHSUNDEEP
javac++recursionstack-overflowflood-fill
LuminousNutria
LuminousNutria

Reputation: 2001

Translating C++ recursive floodfill implementation for 2D array without any loops, into Java?

I am trying to translate a recursive flood-fill implementation that doesn't use any loops. I keep getting a stack overflow error, and I'm not sure why. I have been trying to translate the C++ code here.

How can I fix my Java translation of this code?

C++ original code:

// A recursive function to replace previous color 'prevC' at  '(x, y)'  
// and all surrounding pixels of (x, y) with new color 'newC' and 
void floodFillUtil(int screen[][N], int x, int y, int prevC, int newC) 
{ 
// Base cases 
if (x < 0 || x >= M || y < 0 || y >= N) 
    return; 
if (screen[x][y] != prevC) 
    return; 

// Replace the color at (x, y) 
screen[x][y] = newC; 

// Recur for north, east, south and west 
floodFillUtil(screen, x+1, y, prevC, newC); 
floodFillUtil(screen, x-1, y, prevC, newC); 
floodFillUtil(screen, x, y+1, prevC, newC); 
floodFillUtil(screen, x, y-1, prevC, newC); 
}

my Java floodFill() method:

public void floodFill(int[][] pic, int row, int col, int oldC, int newC) {

  // Base Cases
  if(row < 0 || col < 0 || row >= pic.length - 1 || col >= pic[row].length - 1) {
     return;
  }
  if(pic[row][col] != oldC) {
     return;
  }

  // recursion
  floodFill(pic, row++, col, oldC, newC);
  floodFill(pic, row--, col, oldC, newC);
  floodFill(pic, row, col++, oldC, newC);
  floodFill(pic, row, col--, oldC, newC);
}

Upvotes: 3

Views: 844

Answers (1)

LuminousNutria
LuminousNutria

Reputation: 2001

I needed to put the line pic[row][col] = newC in the program. Another problem was that I didn't know variableName++ is a different command from variableName + 1 so the recursion didn't work as expected. variableName++ returns the value of variableName before it was incremented.

This code allowed my program to work:

public void floodFill(int[][] pic, int row, int col, int oldC, int newC) {

  // Base Cases
  if(row < 0 || col < 0 || row >= pic.length || col >= pic[row].length) {
     return;
  }
  if(pic[row][col] != oldC) {
     return;
  }

  pic[row][col] = newC;

  // recursion
  floodFill(pic, row + 1, col, oldC, newC);
  floodFill(pic, row - 1, col, oldC, newC);
  floodFill(pic, row, col + 1, oldC, newC);
  floodFill(pic, row, col - 1, oldC, newC);
}

Upvotes: 2

Related Questions