recursion - 易递归算法的迭代版本

Question

我想我有一个非常简单的问题。我遇到了这个问题，可以通过递归函数很容易地解决，但我无法迭代解决。

假设您有任何 bool 矩阵，例如:

M:

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

我知道这不是一个普通的 bool 矩阵，但它对我的示例很有用。你可以注意到那里有某种零路径......

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

(就像在 Paint 或任何图像编辑器中绘制区域时一样)

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

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

好吧，我的问题是如何迭代地做到这一点......希望我没有搞砸太多

提前致谢!

曼努埃尔

ps:如果您能用 C、S、python 或伪代码显示该函数，我将不胜感激:D

Answer 1

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

此代码的递归版本看起来像(伪代码 - 没有边界检查):

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-esque，同样，没有边界检查):

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