An alternative way to write this recursive function?

Question

I have a grid of colors (in a 2D ArrayList). I need to be able to count the number of cells that share the same color in a particular color block (they have to be adjacent on 4 edges). I can do this easily recursively, but the problem is that some images Overflow the stack since color blocks can be so big.

Here's the recursive function:

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

Any thoughts on an alternative with loops or something?

Answer 1

The idea is to make the "stack/queue" explicit in your application code. Note that this doesn't use less memory then the recursive approach, it just has more memory to play with by utilizing the heap. The following code is an example. Note that you can call queue.addFirst or queue.addLast, this will not change the end result but will give you different traversals of the board which is something you may or may not care about.

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

Standard way to get rid of recursion is to use Stack data structure, as recursion is essentially a stack manipulation. But in your concrete situation you can use breadth-first search. You can implement it using queue:

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