寫這個遞歸函數的另一種方法是什麼？

Question

我有一個顏色的網格（在二維ArrayList中）。我需要能夠計算特定顏色塊中共享相同顏色的單元格的數量（它們必須在4個邊上相鄰）。我可以很容易地遞歸執行此操作，但問題是某些圖像溢出堆棧，因爲顏色塊可能非常大。

這裏的遞歸函數：

private int getBlockCount(PietCodel codel) { 

    if (codel.getValue() != PietCodel.DEFAULT && codel.getValue() != PietCodel.CHECKED) { 
     return codel.getValue(); 
    } 

    ArrayList<PietCodel> list = blockCountHelper(codel); 
    list.add(codel); 

    // Use the array of codels in the block, and 
    // use the size to for each value in the array. 
    int result = list.size(); 
    for (PietCodel item : list) item.setValue(result); 

    System.out.println("Block count: " + result); 

    return result; 
} 

private ArrayList<PietCodel> blockCountHelper(PietCodel codel) { 
    ArrayList<PietCodel> result = new ArrayList<>(); 
    codel.setValue(PietCodel.CHECKED); 
    int col = codel.getCol(); 
    int row = codel.getRow(); 

    // Right 
    PietCodel ajac = get(col + 1, row); 
    if (ajac != null && codel.equals(ajac.getColor()) && ajac.getValue() == PietCodel.DEFAULT) { 
     ArrayList<PietCodel> nextCodels = blockCountHelper(ajac); 
     result.add(ajac); 
     result.addAll(nextCodels); 
    } 

    // Down 
    ajac = get(col, row + 1); 
    if (ajac != null && codel.equals(ajac.getColor()) && ajac.getValue() == PietCodel.DEFAULT) { 
     ArrayList<PietCodel> nextCodels = blockCountHelper(ajac); 
     result.add(ajac); 
     result.addAll(nextCodels); 
    } 

    // Left 
    ajac = get(col - 1, row); 
    if (ajac != null && codel.equals(ajac.getColor()) && ajac.getValue() == PietCodel.DEFAULT) { 
     ArrayList<PietCodel> nextCodels = blockCountHelper(ajac); 
     result.add(ajac); 
     result.addAll(nextCodels); 
    } 

    // Up 
    ajac = get(col, row - 1); 
    if (ajac != null && codel.equals(ajac.getColor()) && ajac.getValue() == PietCodel.DEFAULT) { 
     ArrayList<PietCodel> nextCodels = blockCountHelper(ajac); 
     result.add(ajac); 
     result.addAll(nextCodels); 
    } 

    return result; 
} 

上環什麼的替代有什麼想法？

Answer 1

這個想法是在應用程序代碼中明確地顯示「堆棧/隊列」。請注意，這不會使用較少的內存，然後遞歸方法，它只是 有更多的內存使用堆玩。以下代碼是一個示例。請注意，您可以撥打queue.addFirst或queue.addLast，這將使 不會改變最終結果，但會爲您提供不同的董事會遍歷，您可能會也可能不會關心。

private ArrayList<PietCodel> blockCountHelper(PietCodel codel) { 
    ArrayList<PietCodel> accumulator = new ArrayList<>(); 
    LinkedList<PietCodel> queue = new LinkedList<>(); 
    queue.add(codel); 

    while (!queue.isEmpty()) { 
      PietCodel ajac = queue.remove(); 
      if (ajac != null && codel.equals(ajac.getColor()) ....) { 
       accumulator.add(ajac); 
      } 
      if (get(col + 1, row) != null) {queue.addFirst(get(col + 1, row));} 
      if (get(col , row + 1) != null) {queue.addFirst(get(col, row + 1));} 
      if (get(col - 1, row) != null) {queue.addFirst(get(col - 1, row));} 
      if (get(col , row - 1) != null) {queue.addFirst(get(col, row- 1));} 
    } 
    return accumulator; 
} 

Answer 2

擺脫遞歸的標準方法是使用Stack數據結構，因爲遞歸本質上是一個堆棧操作。但在具體情況下，您可以使用廣度優先搜索。你可以使用隊列來實現它：

int rows = 10; 
int cols = 10; 
PietCodel codels[][] = new PietCodel[rows][cols]; 
boolean used[][] = new boolean[rows][cols]; 
private void test() { 
    for (int i = 0; i < rows; ++i) { 
     for (int j = 0; j < rows; ++j) { 
      int color = (int) (Math.random() * 3); 

      PietCodel codel = new PietCodel(i, j, color); 

      codels[i][j] = codel; 
      System.out.print(color + " "); 
     } 
     System.out.println(); 
    } 
    System.out.println(); 

    System.out.println(getBlockCount(get(0, 0))); 
} 

private int getBlockCount(PietCodel codel) { 
    used = new boolean[rows][cols]; 

    Queue<PietCodel> q = new LinkedList<>(); 
    q.add(codel); 
    used[codel.getRow()][codel.getCol()] = true; 

    int color = codel.getColor(); 
    int count = 0; 
    while (!q.isEmpty()) { 
     PietCodel ajacent = q.poll(); 
     int col = ajacent.getCol(); 
     int row = ajacent.getRow(); 
     ++count; 

     addColored(q, col + 1, row, color); 
     addColored(q, col - 1, row, color); 
     addColored(q, col, row + 1, color); 
     addColored(q, col, row - 1, color); 
    } 

    return count; 
} 

private PietCodel get(int col, int row) { 
    return col < 0 || col >= cols || row < 0 || row >= rows ? null : codels[row][col]; 
} 

private void addColored(Queue<PietCodel> q, int col, int row, int color) { 
    if (col < 0 || col >= cols || row < 0 || row >= rows) { 
     return; 
    } 

    PietCodel codel = codels[row][col]; 
    if (codel.getColor() != color || used[row][col]) { 
     return; 
    } 

    used[row][col] = true; 
    q.add(codel); 
} 

static class PietCodel { 
    static final int DEFAULT = 0; 
    static final int CHECKED = -1; 
    static final int USED = -2; 
    final int row; 
    final int col; 
    final int color; 
    int value; 

    public PietCodel(int row, int col, int color) { 
     this.col = col; 
     this.row = row; 
     this.color = color; 
    } 

    public int getCol() { 
     return col; 
    } 

    public int getRow() { 
     return row; 
    } 

    public int getValue() { 
     return value; 
    } 

    public void setValue(int value) { 
     this.value = value; 
    } 

    public int getColor() { 
     return color; 
    } 

    public boolean same(PietCodel ajac) { 
     return color == ajac.getColor(); 
    } 
}