易于递归算法的迭代版本

Question

我想问一个很简单的问题。

我遇到了一个问题，可以用递归函数很容易地解决，但我无法迭代地解决它。

假设你有一个布尔矩阵，如下：

M：

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

我知道这不是普通的布尔矩阵，但它对我的示例很有用。你可以看到里面有一些零路径...

我想要创建一个函数，它接收这个矩阵和存储零的点，并将同一区域内的每个零转换为2（假设矩阵可以存储任何整数，即使它最初是布尔值）

（就像在Paint或任何图像编辑器中涂色区域一样）

假设我使用这个矩阵M和右上角零的坐标调用该函数，则结果将是：

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

嗯，我的问题是如何迭代地完成这个操作...希望我没有弄糊涂它太多

提前感谢！

Manuel

附注：如果您能用C、S、Python或伪代码展示函数，我将不胜感激:D

- Manuel

Answer 1

有一种标准技术可以将特定类型的递归算法转换为迭代算法，它被称为尾递归。

这段代码的递归版本如下（伪代码-不包含边界检查）：

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

这不是简单的尾递归（多个递归调用），因此您需要添加某种堆栈结构来处理中间内存。一种版本看起来像这样（伪代码，类似于Java，同样，没有边界检查）：

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

- Nick Fortescue

Answer 2

将递归函数转换为迭代函数的最简单方法是利用堆栈数据结构来存储数据，而不是通过递归调用在“调用堆栈”上存储它。

伪代码：

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*/ )

- chakrit

---

请参见ascobol的帖子的评论 - 从技术上讲，这仍然是递归的。 - Skizz

你使用了和其他人不同的“递归”定义。 - mqp

Answer 3

伪代码：

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)

- schnaader

Answer 4

对于这个问题，我会使用一个栈或队列对象。以下是类似Python的伪代码：

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)

- ascobol

---

使用堆栈/队列对象仍然是递归的，您需要自己管理堆栈，而不是使用编程语言来为您进行清理工作。 - Skizz

错误。递归意味着函数调用或引用自身。http://en.wikipedia.org/wiki/Recursion。我同意你的观点，编译后的代码在功能上是相同的，但这并不严格意义上是递归。一个理由是非递归版本可以在单遍解析器中解析。 - Nick Fortescue

@Nick：在函数式编程中，递归过程是指使用非常量空间进行延迟操作的过程，而迭代过程则使用常量空间。因此，使用堆栈或队列是一种递归过程（http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1）。 - outis

Answer 5

并非所有递归算法都可以转换为迭代算法。通常只有具有单一分支的线性算法才能这样做。这意味着，具有两个或更多分支的树算法和具有更多路径的二维算法极难在不使用堆栈（基本上是作弊）的情况下转换为递归算法。

例如：

递归：

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

迭代：

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

递归：

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

部分迭代（尝试）：

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

正如您所见，有两条路径（左和右）。可以将其中一条路径转换为迭代，但要将另一条路径转换为迭代，则需要保留状态，这可以使用堆栈完成：

迭代（带堆栈）：

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

这个方法可行，但使用递归算法会更容易理解。

- Gamecat

---

每个递归都可以转换为迭代 - 请参阅https://dev59.com/FHNA5IYBdhLWcg3wgeOk - steve

Answer 6

一个简单的迭代方法是使用队列。

1. 将起始点插入队列
2. 从队列获取第一个元素
3. 设置为2
4. 将所有仍然为0的邻居放入队列
5. 如果队列不为空，则跳转到第2步。

- mdm

Answer 7

如果迭代比性能更重要，我会使用以下算法：

1. 设置初始值为2
2. 扫描矩阵以查找靠近2的0
3. 如果找到这样的0，则将其更改为2并重新开始步骤2中的扫描。

这很容易理解，不需要堆栈，但非常耗时。

- mouviciel