iterative version of easy recursive algorithm

Question

I have a quite simple question, I think. I've got this problem, which can be solved very easily with a recursive function, but which I wasn't able to solve iteratively.

Suppose you have any boolean matrix, like:

M:

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

I know this is not an ordinary boolean matrix, but it is useful for my example. You can note there is sort of zero-paths in there...

I want to make a function that receives this matrix and a point where a zero is stored and that transforms every zero in the same area into a 2 (suppose the matrix can store any integer even it is initially boolean)

(just like when you paint a zone in Paint or any image editor)

suppose I call the function with this matrix M and the coordinate of the upper right corner zero, the result would be:

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

well, my question is how to do this iteratively... hope I didn't mess it up too much

Thanks in advance!

Manuel

ps: I'd appreciate if you could show the function in C, S, python, or pseudo-code, please :D

Answer 1

Pseudo-code:

Input: Startpoint (x,y), Array[w][h], Fillcolor f

Array[x][y] = f
bool hasChanged = false;
repeat
  for every Array[x][y] with value f:
    check if the surrounding pixels are 0, if so:
      Change them from 0 to f
      hasChanged = true
until (not hasChanged)

Answer 2

For this I would use a Stack ou Queue object. This is my pseudo-code (python-like):

stack.push(p0)
while stack.size() > 0:
    p = stack.pop()
    matrix[p] = 2
    for each point in Arround(p):
       if matrix[point]==0:
          stack.push(point)

Answer 3

The easiest way to convert a recursive function into an iterative function is to utilize the stack data structure to store the data instead of storing it on the call stack by calling recursively.

Pseudo code:

var s = new Stack();

s.Push( /*upper right point*/ );

while not s.Empty:

    var p = s.Pop()        
    m[ p.x ][ p.y ] = 2

    s.Push ( /*all surrounding 0 pixels*/ )

Answer 4

There is a standard technique for converting particular types of recursive algorithms into iterative ones. It is called tail-recursion.

The recursive version of this code would look like (pseudo code - without bounds checking):

paint(cells, i, j) {
   if(cells[i][j] == 0) {
      cells[i][j] = 2;
      paint(cells, i+1, j);
      paint(cells, i-1, j);
      paint(cells, i, j+1);
      paint(cells, i, j-1);
   }
}

This is not simple tail recursive (more than one recursive call) so you have to add some sort of stack structure to handle the intermediate memory. One version would look like this (pseudo code, java-esque, again, no bounds checking):

paint(cells, i, j) {
    Stack todo = new Stack();
    todo.push((i,j))
    while(!todo.isEmpty()) {
       (r, c) = todo.pop();
       if(cells[r][c] == 0) {
          cells[r][c] = 2;
          todo.push((r+1, c));
          todo.push((r-1, c));
          todo.push((r, c+1));
          todo.push((r, c-1));              
       }          
    }
}

Answer 5

Not all recursive algorithms can be translated to an iterative algorithm. Normally only linear algorithms with a single branch can. This means that tree algorithm which have two or more branches and 2d algorithms with more paths are extremely hard to transfer into recursive without using a stack (which is basically cheating).

Example:

Recursive:

listsum: N* -> N
listsum(n) ==
  if n=[] then 0 
          else hd n + listsum(tl n)

Iteration:

listsum: N* -> N
listsum(n) ==
  res = 0;
  forall i in n do
    res = res + i
  return res

Recursion:

treesum: Tree -> N
treesum(t) ==
  if t=nil then 0
  else let (left, node, right) = t in
    treesum(left) + node + treesum(right)

Partial iteration (try):

treesum: Tree -> N
treesum(t) ==
  res = 0
  while t<>nil 
    let (left, node, right) = t in
      res = res + node + treesum(right)
      t = left
  return res

As you see, there are two paths (left and right). It is possible to turn one of these paths into iteration, but to translate the other into iteration you need to preserve the state which can be done using a stack:

Iteration (with stack):

treesum: Tree -> N
treesum(t) ==
  res = 0

  stack.push(t)
  while not stack.isempty()
    t = stack.pop()
    while t<>nil 
      let (left, node, right) = t in
        stack.pop(right)
        res = res + node + treesum(right)
        t = left

  return res

This works, but a recursive algorithm is much easier to understand.

Answer 6

If doing it iteratively is more important than performance, I would use the following algorithm:

1. Set the initial 2
2. Scan the matrix for finding a 0 near a 2
3. If such a 0 is found, change it to 2 and restart the scan in step 2.

This is easy to understand and needs no stack, but is very time consuming.

Answer 7

A simple way to do this iteratively is using a queue.

1. insert starting point into queue
2. get first element from queue
3. set to 2
4. put all neighbors that are still 0 into queue
5. if queue is not empty jump to 2.