java - 递归时出现StackOverflow错误如何处理？

Question

我目前正在开发一个程序，该程序读取大小为 n * n 的“ map ”。这张“ map ”是由人物.组成的。和* ，其中.代表水，并且 *代表土地。该程序的要点是计算 map 上有多少个“岛屿”，其中“岛屿”是完全被水( * )包围的任何一 block 土地( . )。如果两 block 土地 ( * ) 在传统八个方向中的任何一个方向相连，则它们被视为一个岛屿。作为引用，我将在末尾放置一个示例输入和输出。

我的代码(我还将包括在内)解析 2D char与 map 匹配的数组，递增 int numOfIslands每当遇到 * 。然后它替换 *与 . ，并在继续遍历之前使用递归来查找并替换该“岛”的其余部分。它目前适用于较小的输入大小，例如包含的示例输入。然而，问题是它需要能够在 n = 1000 的输入大小上运行。 ，当我尝试在这么大的输入大小上运行它时，当前会出现 StackOverflow 错误。我应该如何处理 StackOverflow 错误？我想这与递归期间的中断有关，以便“卸载”堆栈，但老实说，我不知道如何开始这样做，而且我的互联网研究也没有什么成果。

我的遍历和递归代码，其中map[][]是一个 2D char与输入文件匹配的数组:

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

示例输入:

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

示例输出:

The total number of islands is 3

Answer 1

在没有详细研究您的算法的情况下，我怀疑您多次检查同一单元格，导致搜索深度呈指数增长。避免这种情况的一个直接但有效的方法是保留已测试单元的缓存，并在找到的地方使用缓存结果。

<小时/>

但是，如果您确实需要那么深的堆栈......

在某些平台上，您可以使用public Thread(ThreadGroup group, Runnable target, String name, long stackSize)来为自己获取一个可以访问更多堆栈的线程。

但是 Javadoc 警告:“在某些平台上，stackSize 参数的值可能没有任何效果。”

<小时/>

如果一个算法确实需要栈，但JRE的调用栈太小，你可以将其翻译成在堆内存中使用自己的栈的版本。

例如，这是使用递归的古老经典汉诺塔:

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

您可以执行等效操作:

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

它不是递归的，因此它不会创建深层调用堆栈。但它仍然使用相同的原理，即使用 LIFO 堆栈作为“待办事项列表”，只不过现在 LIFO 数据结构是堆的一部分。