Turning multiple-recursion method into iteration

Question

I know that a similar answer has been asked many times, but my case isn't that simple.

I have a recursive method which can call itself 4 times ("Worst case"). I'm trying hard to avoid recursion since it leads to a StackOverFlowException but I cannot find a way to replace it with a while loop or something similar.

Is this even possible? As far as I've come with my knowledge, you can only move in one direction using a while loop instead of "flowing" in all directions (depth-first-search in reality).

Here is the code:

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

What I am doing here:

1. In a "binary picture" (here in the example it's turned into a 2D-int Array) I'm looking for black pixels around a specific one until I got all connected black pixels.
2. Black has the value of 1, white has the value of 0. Pixels that I already visited will be set to value 2 (for later processing).
3. This algorithm makes a "depht-first search" until all connected black pixels (side-by-side) have been found

Answer 1

You can always avoid a recursion by using a Stack :

• instead of making a recursive call to searchNeighboringPixels(x, y, arr), put the point (x,y) in a Stack.

• wrap your 4 conditions with a while loop, which runs until the Stack is empty.

• each iteration pops the top of the Stack, and treats that point as the current point.

Something like this :

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

You say that you're doing a depth first search. There are many well defined iterative approaches to this problem, most of them based off some form of a Queue or a Stack held locally in the method rather than the call stack. The advantage of a queue based approach, as you have figured out, is that the Queue does not suffer from the same limitations on stack space that a recursive solution does.

Pseudocode for a this sort depth first search 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)