Home > front end >  Can anyone please tell me why my flood fill is causing stackoverflow error?
Can anyone please tell me why my flood fill is causing stackoverflow error?

Time:12-10

public static int flood(int x, int y) {
    if(x<0||y<0||x>101||y>101||went[x][y]) return 0;
    System.out.println(x   " "    y);
    went[x][y] = true;
    if(grid[x][y] == 1) return 1;
    int result = 0;
    result  = flood(x 1,y);
    result  = flood(x,y 1);
    result  = flood(x-1,y);
    result  = flood(x,y-1);
    return result;
}

The code never came back to the same coordinate, but it is still somehow crashing.

P.S. went is a 2d boolean array.

CodePudding user response:

What you wrote is a recursive function, it calls itself.

At first sight, it looks ok, but it "expands very fast".

In the first call to flood(0,0), it will "stack" flood(1,0) which will then "stack" flood(2,0) ... which will then stack flood(100,100) and only at this point will the method return for the first time!

That means that the stack size is roughly 10000 before the stack (of methods to continue processing once the current one is done) starts to "shrink back" after that point.

The basics of your method is correct, and I suppose it will work for a small array size, it's just a too big stack for a default JVM.

  • Related