递归题--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

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

如果您想避免使用太多内存，可以使用列出的众多洪水填充算法之一在 Wikipedia 上，例如扫描线填充。

Answer 2

如果您收到 StackOverflowError，则您的递归深度可能太大。如果可以的话，考虑采用迭代方法。

您还可以增加 JVM 的堆栈大小，而不是堆大小。为此，请将 -Xss 参数设置为 JVM。例如，-Xss2048k。

Answer 3

这里的主要问题是，由于许多基于堆栈的内存系统的性质，每次调用都会为该方法调用创建一个新堆栈，并且由于没有尾端递归优化，这意味着每个递归调用都会创建一个新堆栈。最好的选择可能是将方程更改为循环而不是递归。