Recursion Question--Java

Question

Ok so I have a recursion problem thats causing a stack overflow error at large sizes I increased the heap size to like it works fine at smaller sizes. The problem is to find the largest contiguous group of cells with 1 or more adults in a 2d- array.

public class Field {
    Cell[][] cells;
    public Field(Cell[][] cells){
        this.cells=cells;
    }
    /**
     * Sort by what's connected--> recursive helper (rec)
     * @return rank value of 
     */
    int findCore(){
        //Reset ranks
        for(int i=0; i<cells.length; i++)
            for(int j=0; j<cells[0].length; j++)
                cells[i][j].setRank(-1);

        int counter = 0;
        for(int i=0; i<cells.length; i++){
            for(int j=0; j<cells[0].length; j++){
                if(cells[i][j].getRank()==-1 && cells[i][j].getNAdults()>0){
                    rec(i,j, counter);
                    counter++;              
                }
            }
        }
        return findLargest(counter);
    }
    /**
     * Recursive function helper, Gives every group a unique id
     * @param x
     * @param y
     * @param col
     * @return
     */
    void rec(int x, int y, int col){
        if(cells[x][y].getRank()==-1){
            cells[x][y].setRank(col);
            for(int i=-1; i<=1; ++i)
                for(int j=-1; j<=1; ++j)
                    if((x+i)>=0 && (y+j)>=0  && (x+i) < (cells.length) && (y+j)< (cells[0].length))
                        if(cells[x+i][y+j].getNAdults() > 0 && cells[x+i][y+j].getRank() == -1){
                            rec(x+i, y+j, col);
                            break;
                        }
        }
    }
    /**
     * Take all the groups in the field and figure out which one is the largest
     * @param numGroups
     * @return (groupid)
     */
    int findLargest(int numGroups){
        int[] numArray = new int[numGroups];
        for(int i=0; i<cells.length; i++)
            for(int j=0; j<cells[0].length; j++)
                if(cells[i][j].getRank()!=-1)
                    numArray[cells[i][j].getRank()]++;

        int max=0;
        for(int i=0; i<numArray.length; i++)
            if(numArray[i]>numArray[max])
                max=i;

        return max;
    }
    //Test Field functions
    public static void main(String[] args){
        int xSize = 1000;
        int ySize = 1000;
        Field fd = new Field(new Cell[xSize][ySize]);
        for(int i=0; i<xSize; ++i){
            for(int j=0; j<ySize; ++j)
                //if(i==0 || i ==3 || i==1)
                    fd.cells[i][j] = new Cell(1,1,1);
                //else
                    //fd.cells[i][j] = new Cell();
        }
        System.out.println("Largest Group: "  + fd.findCore());
        for(int i=0; i<xSize; ++i){
            for(int j=0; j<ySize; ++j){
                System.out.print(fd.cells[i][j].getRank() + "\t");
            }
            System.out.print("\n");
        }

    }
}

Answer 1

If you're getting a StackOverflowError, then your recursion depth is probably too great. Consider going to an iterative approach if you can.

You can also increase the stack size rather than the heap size for the JVM. To do this, set the -Xss argument to the JVM. For example, -Xss2048k.

Answer 2

The main issue here is that due to the nature of many stack based memory systems, every call creates a new stack for that method call, and as there is no tail-end recursion optimizations that means that each recursive call creates a new stack. What might be your best bet is to change the equation to just a loop as opposed to recursion.

Answer 3

You can implement recursion "manually" by using a stack. At each step you push on your current state and then pop it again when you unwind. If you use your own stack instead of the call stack it can be much larger and you won't get stack overflow exceptions.

If you want to avoid using so much memory you can use one of the many flood fill algorithms listed on Wikipedia, for example scanline fill.