Stack Overflow Error in a Self Calling Function in Java (Number of Islands)

Question

I did some research on what causes a stack overflow errors, and I can conclude it is being caused by a recursive function in a program that is supposed to "count the number of islands" in an array. I understand what is causing the issue, but not sure why this is happening, or my main question is what to actually do about it. I found that if I slow down the program by having it repeatedly printing out something to the console, it works, but it takes forever to complete. Is there a way I can keep the program speed without the error, or a better way to solve the problem (search up "number of islands" to find the problem). Also, the array is two dimensional with a size of 1050 by 800.

public class NumOfIslands {
  static boolean[][] dotMap = new boolean[1050][800];
  static boolean visited[][] = new boolean[1050][800];
  static int total = 0;
  public static void main(String args[]) {
    defineArrays();
    run();
  }
  public static void findObjects(int xCord, int yCord) {
    for(int y = yCord - 1; y <= yCord + 1; y++) {
      for(int x = xCord - 1; x <= xCord + 1; x++) {
        if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
          if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
            visited[x][y] = true;
            findObjects(x,y);
            //System.out.println("test");
          }
        }
      }
    }
  }
  public static void defineArrays() {
    for(int y = 0; y < 800; y++) {
      for(int x = 0; x < 1050; x++) {
        dotMap[x][y] = true;
      }
    }
  }

  public static int run() {
    //dotMap = DisplayImage.isYellow;
    System.out.println(dotMap.length + " " + dotMap[0].length);
    int objects = 0;
    for(int y = 439; y < 560/*dotMap[0].length*/; y++) {
      for(int x = 70; x < 300/*dotMap.length*/; x++) {
        if(dotMap[x][y] == true && visited[x][y] != true) {
          visited[x][y] = true;
          objects++;
          findObjects(x,y);
        }
      }
    }
    System.out.println("total" + total);
    System.out.println(objects);
    return objects;

  }
}

@ScaryWombat The for loop is used to check every value inside the error. If any value is reached using the recursive function, then a seperate array stores that it was visited. The reason I need the loop is because I am counting the number of objects connected in an array, and I know its going to be more than one so I think I need the loop and the function. There may be a better way to do this that I am missing. — Luke Darcy, Oct 30 '18 at 02:01
But as you seem to be visiting every element based upon your nested for loops, do you need to call the method recursively? — Scary Wombat, Oct 30 '18 at 02:05
@ScaryWombat I think It does need the nested loop and the recursion because the program checks ever unvisited coordinate/value, and if it is 1/true, it branches out to find all other connected values. Once it finds these connected values, it continues the loop looking for the next unvisited value that was not connected to the previous "object." — Luke Darcy, Oct 30 '18 at 02:10

uli · Accepted Answer · 2018-10-30T16:27:50.790

StackOverflowError reasons. In your example each call to findObjects adds 2 variables to the stack int x and int y from loops.

One of the fastest solution:

class Solution {
    int m, n;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int counter = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    visit(grid, i, j);
                    counter++;
                }
            }
        }
        return counter;
    }

    public void visit(char[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        visit(grid, i - 1, j);
        visit(grid, i + 1, j);
        visit(grid, i, j - 1);
        visit(grid, i, j + 1);
    }
}

All recursive algorithms can be implemented with loops. One of the example is below. The Solution implements BFS (Breadth-first search) algorithm, more details on wikipedia.

class Solution {
  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;

    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          Queue<Integer> neighbors = new LinkedList<>();
          neighbors.add(r * nc + c);
          while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.add((row-1) * nc + col);
              grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.add((row+1) * nc + col);
              grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.add(row * nc + col-1);
              grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.add(row * nc + col+1);
              grid[row][col+1] = '0';
            }
          }
        }
      }
    }
    return num_islands;
  }
}

I tried running your code but I got the same stack overflow error. I am using Dr Java though because this is a school computer and I cannot get something more powerful. Not sure if a program like android studios or eclipse would still encounter this. Because this is used in terms each pixel on an image, it is a large for loop (x = 1050 and y = 800). — Luke Darcy, Oct 30 '18 at 13:57
Tried it with lower resources and caught your error). Added iterative example. The trick is to use Queue (LinkedList) to store discovered neighbors, to visit them on next loop of while. — uli, Oct 30 '18 at 16:30
I adapted the second program you put in into my code and it seem to be working really well. I dont' really understand how linked lists work though, so I will do more research on that. Thanks for your response. — Luke Darcy, Oct 31 '18 at 02:33

score 0 · Answer 2 · answered Oct 30 '18 at 04:23

the problem is in this function

public static void findObjects(int xCord, int yCord) {


        for(int y = yCord - 1; y <= yCord + 1; y++) {
          for(int x = xCord - 1; x <= xCord + 1; x++) {
            if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
              if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
                visited[x][y] = true;
                 findObjects(x,y);
                //System.out.println("test");
              }
            }
          }
        }
      }`

at here you are builiding a stack of recursive calls to findobjects and ultimately it has no termination condition so it ends up at infinite stacks of findobjects, so my solution is if you are just checking that if x and y varaibles are not equal and visited[x][y] is not true then there is no need to call for recursion just comment the recursive call, because your loop already do what you want the recursive call to do.

 public static void findObjects(int xCord, int yCord) {


        for(int y = yCord - 1; y <= yCord + 1; y++) {
          for(int x = xCord - 1; x <= xCord + 1; x++) {
            if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length) {
              if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true) {
                visited[x][y] = true;
                //findObjects(x,y);
                //System.out.println("test");
              }
            }
          }
        }
      }

You are wrong. First, `findObjects` has termination conditions `if(x > -1 && y > -1 && x < dotMap[0].length && y < dotMap.length)` and `if((x != xCord || y != yCord) && dotMap[x][y] == true && visited[x][y] != true)`. Second, your change will not mark the entire island and results in incorrect count of `objects` in `run()` function. — uli, Oct 30 '18 at 04:30
in method **findobjects** you are checking that each position of visited array that it is visited or not so your inner and outher loop already do that in method **findobjects** so why do you need to call **findobjects** recusively ? — Ömer, Oct 30 '18 at 04:50
Goal of the findObjects is to mark the entire island (all connected cells). Loops in findObjects method only checks cells in radius of 1 cell. Loops in run function starts from middle of the array, however island occupies entire array. — uli, Oct 30 '18 at 04:58

Stack Overflow Error in a Self Calling Function in Java (Number of Islands)

2 Answers2