写这个递归函数的另一种方法是什么？

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(); 
    } 
}