How to properly use recursion in this function?

Question

ok, i have this function that needs to use recursion, to search in a mineswepper(int[][] m) given a coordinate(i, j) by the user, a zero. The zero means there is no mines near that localition. If it is a zero, then my function should show this zero and the zeros around this initial zero in a range of one localition. This has to be made in a recursive way, for all the zeros found.

My int[][]v is my vision matrix, it used to give and status(1 => you can show the location, 0 => keep the ?) for all the locations individually, so when i print all the matrix m we can only see the locations that have a 1 in the matrix v.

1-. Found a zero2

2-. Search around to find other zeros, until there is no more zero to found

?   ?   ?   ?
?   ?   ?   ?
?   ?   0   ?
?   ?   ?   ?
?   ?   ?   ?

how it would look like in the vision matrix v

0   0   0   0
0   0   0   0
0   0   1   0
0   0   0   0
0   0   0   0



?   ?   ?   ?
?   ?   ?   ?
?   ?   0   ?
?   ?   ?   0
?   ?   ?   ?

how it would look like in the vision matrix v

0   0   0   0
0   0   0   0
0   0   1   0
0   0   0   1
0   0   0   0

 public void zeros(int[][]m, int[][]v, int j, int i){

            v[i][j] = 1;

            for(int a = Math.max(0, i-1); a < Math.min(5,i+2); a++){
              for(int b = Math.max(0,j-1); b < Math.min(5,j+2); b++){
                 if(m[a][b] == 0){
                     i = a;
                     j = b;
                    zeros( m, v, i, j);}

                }
            }         
   }

The fors are to searh in all the locations around the given i and j.

It shows me errors, Exception in thread "main" java.lang.StackOverflowError. I dont get it why. Maybe someone could give a way eary to make the recursivity, or tell me my mistake.

Answer 1

so far all good. but fix the following

remove those two lines:

i = a;
j = b;

call it as follow:

zeros( m, v, a, b);

instead of:

zeros( m, v, i, j);

also change this:

public void zeros(int[][]m, int[][]v, int j, int i)

too:

public void zeros(int[][]m, int[][]v, int i, int j)

do this to:

if(m[a][b] == 0 && v[a][b]==0)

Answer 2

Consider my solution using movement constant:

int [] movx ={-1, -1, -1, 0, 0, 1, 1, 1};
int [] movy ={-1, 0, 1, -1, 1, -1, 0, 1};

This are the offset you move from (x,y). So your method will be

public void zeros(int[][] m, int[][] v, int x, int y) {

    //Already visited?  
    if (v[x][y] == 1) return;

    //Mark as visited   
    v[x][y] = 1;

    for (int i = 0; i < 8; i++){
        //neighbors coordinates
        int nx = x + movx[i];
        int ny = y + movy[i];

         //check boundaries
         if (nx >= 0 && nx < m.length && ny >= 0 && ny < m[x].length){

             //if there is no mine check it
             if (m[nx][ny] == 0)
                 zeros(m, v, nx, ny);
         }
    }               
}

for example if you have (x=2,y=2) your neighbors will be:

(x=1,y=1)
(x=1,y=2)
(x=1,y=3)
(x=2,y=1)
(x=2,y=2)
(x=2,y=3)
(x=3,y=1)
(x=3,y=2)
(x=3,y=3)

Answer 3

This sounds very similar to a Flood Fill operation. Wikipedia has some meta-code to accomplish this. It's not recursive, but should work well.

Answer 4

The error java.lang.StackOverflowError is one of the most common ones when dealing with recursion. It means that you created an infinite loop in your recursion, and the stack isn't big enough to handle all the recursive calls.

Think about what happens when you recursively call your function on surrounding squares. Because you don't edit the original square, it get's called again, creating an infinite loop.

Fix this and your problem is solved.

Answer 5

Before you do "m[a][b] == 0", you need to do a check to make sure that a and b aren't outside the bounds of m. I don't think you're doing that check currently.

Answer 6

You are passing i and j recursively, but you don't modify the values of these variables, so the call will occur indefinitely

Answer 7

I think that i get it.

just adding this extra condition in the if of the fors.

if(m[a][b] == 0 && v[a][b]!= 1)

so we can not return to any location that has a 1 in the matrix vision v