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

Question

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

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

这可能吗？据我所知，您只能使用 while 循环向一个方向移动，而不是向所有方向移动 "flowing"（现实中是深度优先搜索）。

代码如下：

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

我在这里做什么：

在 "binary picture" 中（在此示例中，它变成了二维整数数组）我正在寻找特定像素周围的黑色像素，直到找到所有连接的黑色像素。
黑色的值为 1，白色的值为 0。我已经访问过的像素将被设置为值 2（供以后处理）。
此算法会生成 "depht-first search"，直到找到所有连接的黑色像素（并排）

Answer 1

您始终可以通过使用堆栈来避免递归：

不是对 searchNeighboringPixels(x, y, arr) 进行递归调用，而是将点 (x,y) 放入堆栈中。
用一个 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
        }
    }
}

Answer 2

你说你在做深度优先搜索。有许多明确定义的迭代方法可以解决这个问题，其中大多数基于某种形式的 Queue 或 Stack 本地保存在方法中而不是调用堆栈中。正如您已经发现的那样，基于队列的方法的优点是队列不会受到与递归解决方案相同的堆栈限制space。

这种排序深度优先搜索的伪代码taken from wikipedia:

A non-recursive implementation of DFS:[6]

Input: A graph G and a vertex v of G

Output: All vertices reachable from v labeled as discovered
1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

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

Turning multiple-recursion method into iteration

java

stack-overflow

iteration

recursion