遞歸堆棧溢出和奇數對象參考Java

Question

private boolean[][] computeMainOutline(boolean[][] outline) { 

    int pixelValue[][] = new int [width][height]; 

    for(int x = 0; x < width; x++) 
     for(int y = 0; y < height; y++) 
      if(pixelValue[x][y] == 0) { 
      ArrayList<Point2D.Double> path = new ArrayList<>(); 
      findPath(x, y, outline, pixelValue, path); 
      } 
    return new boolean[1][1]; // to avoid compilation error 
} 

private void findPath(int x, int y, boolean[][] outline, int pixelValue [][], ArrayList<Point2D.Double> path) { 
    path.add(new Point2D.Double(x, y)); 

    if(x > 0 && outline[x - 1][y] == true) // check right 
     findPath(x - 1, y, outline, pixelValue, path); 
    if(x < width && outline[x + 1][y] == true) // check left 
     findPath(x + 1, y, outline, pixelValue, path); 
    if(y < height && outline[x][y + 1] == true) // check up 
     findPath(x, y + 1, outline, pixelValue, path); 
    if(y > 0 && outline[x][y - 1] == true) // check down 
     findPath(x, y - 1, outline, pixelValue, path); 
} 

上述方法給出StackOverflowError，我不知道爲什麼。

方法computeMainOutline遍歷整個outline數組和pixelValue數組，這兩個數組的大小相同。如果沒有爲特定座標計算「值」，那麼findPath函數將遞歸地計算路徑。路徑基本上是多少個「真」數組元素彼此相鄰。計算值的方法沒有添加，但我的第一個問題是找到路徑。

此外，如果我在path.add(new Point2D.Double(x, y));之後立即打印path.add(new Point2D.Double(x, y));打印path.size()內部的遞歸方法，大小順序不一致它可能會打印（1,2,3,4,2,3,4），爲什麼？

UPDATE

更正像這樣，但它仍然會引發一個堆棧溢出...

private boolean[][] computeMainOutline(boolean[][] outline) { 

    int pixelValue[][] = new int [width][height]; 
    boolean visited[][] = new boolean[width][height]; 

    for(int x = 0; x < width; x++) 
     for(int y = 0; y < height; y++) 
      if(visited[x][y] == false) { 
      ArrayList<Point2D.Double> path = new ArrayList<>(); 
      findPath(x, y, outline, pixelValue, path, visited); 
      } 
    return new boolean[1][1]; // to avoid compilation error 
} 

private void findPath(int x, int y, boolean[][] outline, int pixelValue [][], ArrayList<Point2D.Double> path, boolean visited [][]) { 
    path.add(new Point2D.Double(x, y)); 
    visited[x][y] = true; 

    if(x > 0 && visited[x - 1][y] == false && outline[x - 1][y] == true) // check right 
     findPath(x - 1, y, outline, pixelValue, path, visited); 
    if(x < width - 1 &&visited[x + 1][y] == false && outline[x + 1][y] == true) // check left 
     findPath(x + 1, y, outline, pixelValue, path, visited); 
    if(y < height - 1 && visited[x][y + 1] == false && outline[x][y + 1] == true) // check up 
     findPath(x, y + 1, outline, pixelValue, path, visited); 
    if(y > 0 && visited[x][y - 1] == false && outline[x][y - 1] == true) // check down 
     findPath(x, y - 1, outline, pixelValue, path, visited); 
} 

Answer 1

你做你的遞歸的方式是錯誤的。在進行遞歸方法的同時，每次調用都將先前的調用放在堆棧上。如果你是遞歸運行，那麼堆棧中沒有足夠的空間去更深一層，導致堆棧溢出。

這是問題所在。您沒有在每個時間步驟標記訪問過的內容。想象一下，這是你的網格。引號中的細胞是我們的方法

"T" F F     T F F    "T" F F 
T F F (next step) "T" F F (next)  T F F 
T F F     T F F    T F F 

它可以追溯到它已經訪問過的國家的(x,y)。因此，您將在堆棧中放入無限的方法調用。

解決方案

傳遞另一個數組與已經訪問過的細胞的方法，當你去一個細胞將其標記爲參觀。這可以避免你回到之前看過的東西