How to deal with StackOverflow errors when recursing?

Question

I'm currently working on a program that reads in a "map" of size n * n. This "map" is made of characters . and *, where . represents water, and * represents land. The point of the program is to count how many "islands" occur on the map, where an "island" is any piece(s) of land (*) that is entirely surrounded by water (.). If two pieces of land (*) are connected in any of the traditional eight directions, they are considered one island. For reference, I'll put a sample input and output at the end.

My code, which I'll also include, parses a 2D char array that matches the map, incrementing int numOfIslands whenever it encounters a *. It then replaces that * with ., and uses recursion to find and replace the rest of that "island", before moving on with the traversal. It currently works with smaller input sizes, such as the sample input included. The problem, however, is that it needs to be able to run on an input size of n = 1000, and I currently get StackOverflow errors when I try to run it on an input size that large. What should I do to deal with the StackOverflow errors? I imagine it has something to do with breaking during the recursion, in order to "unload" the stack, but I honestly have no idea how to begin doing that, and my internet research has been less than fruitful.

My traversal and recursion code, where map[][] is a 2D char array that matches the input file:

//traverses the map, looking for 1s, and then sets that location to 0 before running testLocation on it
public static void traverse() {
    for (int col = 0; col < n; col++) {
        for (int row = 0; row < n; row++) {
            if (map[row][col] == '*') {
                map[row][col] = '.';
                testLocation(row, col);
                numOfIslands++;
            }
        }
    }
}    

//takes in a land location, and makes that land, along with the rest of the "island" 0s
public static void testLocation(int row, int col) {
    //test upper left
    if (row > 0 && col > 0) {
        if (map[row - 1][col - 1] == '*') {
            map[row - 1][col - 1] = '.';
            testLocation(row - 1, col - 1);
        }
    }

    //test upper
    if (row > 0) {
        if (map[row - 1][col] == '*') {
            map[row - 1][col] = '.';
            testLocation(row - 1, col);
        }
    }

    //test upper right
    if (row > 0 && col < n - 1) {
        if (map[row - 1][col + 1] == '*') {
            map[row - 1][col + 1] = '.';
            testLocation(row - 1, col + 1);
        }
    }

    //test left
    if (col > 0) {
        if (map[row][col - 1] == '*') {
            map[row][col - 1] = '.';
            testLocation(row, col - 1);
        }
    }

    //test right
    if (col < n - 1) {
        if (map[row][col + 1] == '*') {
            map[row][col + 1] = '.';
            testLocation(row, col + 1);
        }
    }

    //test lower left
    if (row < n - 1 && col > 0) {
        if (map[row + 1][col - 1] == '*') {
            map[row + 1][col - 1] = '.';
            testLocation(row + 1, col - 1);
        }
    }

    //test lower
    if (row < n - 1) {
        if (map[row + 1][col] == '*') {
            map[row + 1][col] = '.';
            testLocation(row + 1, col);
        }
    }

    //test lower right
    if (row < n - 1 && col < n - 1) {
        if (map[row + 1][col + 1] == '*') {
            map[row + 1][col + 1] = '.';
            testLocation(row + 1, col + 1);
        }
    }
}

Sample input:

...*.
**..*
*....
*.*.*
**...

Sample output:

The total number of islands is 3

Answer 1

Without studying your algorithm in too much detail, I have a suspicion that you're checking the same cell more than once, causing exponential growth in the depth of the search. A blunt but effective way to avoid this is to keep a cache of already-tested cells, and use use cached results where found.

---

However if you really do need that deep a stack...

On some platforms, you can use public Thread(ThreadGroup group, Runnable target, String name, long stackSize) to get yourself a thread with access to more stack.

However the Javadoc warns: "On some platforms, the value of the stackSize parameter may have no effect whatsoever."

---

If an algorithm definitely needs a stack, but the JRE's call stack is too small, you can translate it into a version that uses its own stack in heap memory.

For example here's the old classic Tower of Hanoi using recursion:

void move(int num, int from, int to, int using) {
    if(num == 1) {
        println("%d to %d\n", from, to);
    } else {
        move(num-1, from, using, to);
        move(1, from, to, using);
        move(num-1, using, to, from);
    }
}

You can do the equivalent as:

Stack<Task> stack = new Stack<>();
stack.push(new Task(num, from, to, using));
while(!s.empty()) {
    doTask(stack);
}

void doTask(Stack<Task> stack) {
    Task t = stack.pop();

    if t.num == 1 {
        printf("%d to %d\n", from, to);
    } else {
        stack.push(new Task(t.num-1, t.using, t.to, t.from));
        stack.push(new Task(1, t.from, t.to, t.using));
        stack.push(new Task(t.num-1, t.from, t.using, t.to));
    }
}

It's not recursive, so it doesn't create a deep call stack. But it still uses the same principle of using a LIFO stack as a "to-do list", except now the LIFO data structure is part of the heap.