java - 递归题--Java

Question

好的，所以我遇到了一个递归问题，它导致大尺寸时出现堆栈溢出错误，我增加了堆的大小，使其在较小的尺寸下也能正常工作。问题是在二维数组中找到具有 1 个或多个成人的最大连续单元格组。

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

您可以使用堆栈“手动”实现递归。在每一步中，您都会插入当前状态，然后在放松时再次弹出。如果您使用自己的堆栈而不是调用堆栈，它可能会更大，并且不会出现堆栈溢出异常。

如果您想避免使用太多内存，您可以使用众多 flood fill algorithms 中的一种。在维基百科上列出，例如 scanline fill .