java - 将多重递归方法转化为迭代

Question

我知道类似的答案已被问过很多次，但我的情况并不那么简单。

我有一个可以调用自身 4 次的递归方法(“最坏情况”)。我正在努力避免递归，因为它会导致 StackOverFlowException，但我找不到用 while 循环或类似东西替换它的方法。

这可能吗？据我所知，您只能使用 while 循环向一个方向移动，而不是向所有方向“流动”(实际上是深度优先搜索)。

代码如下:

private static void searchNeighboringPixels(int x, int y, int[][] arr) {
        arr[y][x] = 2;
        if (x+1 < arr[y].length && arr[y][x+1] == 1) {
            searchNeighboringPixels(x+1, y, arr);
            //...do other things
        }
        if (x-1 > 0 && arr[y][x-1] == 1) {
            searchNeighboringPixels(x-1, y, arr);
            //...do other things
        }
        if (y+1 < arr.length && arr[y+1][x] == 1) {
            searchNeighboringPixels(x, y+1, arr);
            //...do other things
        }
        if (y-1 > 0 && arr[y-1][x] == 1) {
            searchNeighboringPixels(x, y-1, arr);
            //...do other things
        }
    }

我在这里做什么:

1. 在“二进制图片”中(在此示例中，它变成了 2D-int 数组)我正在寻找特定图片周围的黑色像素，直到找到所有连接的黑色像素。
2. 黑色的值为 1，白色的值为 0。我已经访问过的像素将设置为值 2(供以后处理)。
3. 该算法进行“深度优先搜索”，直到找到所有连接的黑色像素(并排)

Answer 1

你总是可以通过使用堆栈来避免递归:

• 不是对 searchNeighboringPixels(x, y, arr) 进行递归调用，而是将点 (x,y) 放入 Stack 中。

• 用一个 while 循环包装您的 4 个条件，该循环一直运行到 Stack 为空。

• 每次迭代都会弹出 Stack 的顶部，并将该点视为当前点。

像这样:

private static void searchNeighboringPixels(int x, int y, int[][] arr) {
    Stack<Point> points = new Stack<>();
    points.push(new Point(x,y));
    while (!points.isEmpty()) {
        Point p = points.pop();
        x = p.getX();
        y = p.getY();
        arr[y][x] = 2;
        if (x+1 < arr[y].length && arr[y][x+1] == 1) {
            points.push(new Point(x+1,y);
            //...do other things
        }
        if (x-1 > 0 && arr[y][x-1] == 1) {
            points.push(new Point(x-1,y);
            //...do other things
        }
        if (y+1 < arr.length && arr[y+1][x] == 1) {
            points.push(new Point(x,y+1);
            //...do other things
        }
        if (y-1 > 0 && arr[y-1][x] == 1) {
            points.push(new Point(x,y-1);
            //...do other things
        }
    }
}