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