417

我在多年的编程中使用了很多递归来解决简单的问题,但我完全意识到有时由于内存/速度问题您需要迭代。

因此,在很久以前的某个时候,我去尝试查找是否存在将通用递归方法转换为迭代的任何“模式”或教科书方法,但一无所获。或者至少我记得没有任何帮助。

  • 有一般规则吗?
  • 有“模式”吗?
4

21 回答 21

395

通常,我通过将通常传递给递归函数的参数推入堆栈来用迭代算法替换递归算法。事实上,您正在用自己的程序堆栈替换程序堆栈。

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

注意:如果内部有多个递归调用并且想要保留调用的顺序,则必须以相反的顺序将它们添加到堆栈中:

foo(first);
foo(second);

必须替换为

stack.push(second);
stack.push(first);

编辑:文章堆栈和递归消除(或文章备份链接)详细介绍了这个主题。

于 2008-10-01T21:12:30.660 回答
85

实际上,最常见的方法是保留自己的堆栈。这是 C 中的递归快速排序函数:

void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;

    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

以下是我们如何通过保留自己的堆栈来使其迭代:

void quicksort(int *array, int left, int right)
{
    int stack[1024];
    int i=0;

    stack[i++] = left;
    stack[i++] = right;

    while (i > 0)
    {
        right = stack[--i];
        left = stack[--i];

        if (left >= right)
             continue;

        int index = partition(array, left, right);
        stack[i++] = left;
        stack[i++] = index - 1;
        stack[i++] = index + 1;
        stack[i++] = right;
    }
}

显然,这个例子没有检查堆栈边界......实际上你可以根据给定左右值的最坏情况来调整堆栈大小。但你明白了。

于 2008-10-01T20:55:03.197 回答
64

似乎没有人解决递归函数在主体中多次调用自身的位置,并处理返回到递归中的特定点(即不是原始递归)。据说每次递归都可以变成迭代,看来这应该是可以的。

我刚刚想出了一个如何做到这一点的 C# 示例。假设您有以下递归函数,它的作用类似于后序遍历,并且 AbcTreeNode 是具有指针 a、b、c 的三叉树。

public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
        if (x != null) {
            AbcRecursiveTraversal(x.a, list);
            AbcRecursiveTraversal(x.b, list);
            AbcRecursiveTraversal(x.c, list);
            list.Add(x.key);//finally visit root
        }
}

迭代解决方案:

        int? address = null;
        AbcTreeNode x = null;
        x = root;
        address = A;
        stack.Push(x);
        stack.Push(null)    

        while (stack.Count > 0) {
            bool @return = x == null;

            if (@return == false) {

                switch (address) {
                    case A://   
                        stack.Push(x);
                        stack.Push(B);
                        x = x.a;
                        address = A;
                        break;
                    case B:
                        stack.Push(x);
                        stack.Push(C);
                        x = x.b;
                        address = A;
                        break;
                    case C:
                        stack.Push(x);
                        stack.Push(null);
                        x = x.c;
                        address = A;
                        break;
                    case null:
                        list_iterative.Add(x.key);
                        @return = true;
                        break;
                }

            }


            if (@return == true) {
                address = (int?)stack.Pop();
                x = (AbcTreeNode)stack.Pop();
            }


        }
于 2011-12-14T21:42:35.173 回答
36

努力进行递归调用Tail Recursion(最后一条语句是递归调用的递归)。一旦你有了它,将它转换为迭代通常很容易。

于 2008-10-01T20:45:32.877 回答
22

好吧,一般来说,递归可以通过简单地使用存储变量来模拟为迭代。请注意,递归和迭代通常是等价的;一个几乎总是可以转换为另一个。尾递归函数很容易转换为迭代函数。只需将累加器变量设为本地变量,然后迭代而不是递归。这是 C++ 中的一个示例(如果 C 不是为了使用默认参数):

// tail-recursive
int factorial (int n, int acc = 1)
{
  if (n == 1)
    return acc;
  else
    return factorial(n - 1, acc * n);
}

// iterative
int factorial (int n)
{
  int acc = 1;
  for (; n > 1; --n)
    acc *= n;
  return acc;
}

了解我,我可能在代码中犯了一个错误,但想法就在那里。

于 2008-10-01T20:53:27.960 回答
16

即使使用堆栈也不会将递归算法转换为迭代。普通递归是基于函数的递归,如果我们使用堆栈,那么它就变成了基于堆栈的递归。但它仍然是递归的。

对于递归算法,空间复杂度为 O(N),时间复杂度为 O(N)。对于迭代算法,空间复杂度为 O(1),时间复杂度为 O(N)。

但是,如果我们使用堆栈,那么复杂性仍然是一样的。我认为只有尾递归可以转换为迭代。

于 2010-11-06T16:27:11.603 回答
14

堆栈和递归消除文章捕获了在堆上外部化堆栈帧的想法,但没有提供一种直接且可重复的转换方式。下面是一个。

在转换为迭代代码时,必须注意递归调用可能来自任意深度的代码块。它不仅是参数,还有返回到仍有待执行的逻辑的点以及参与后续条件的变量的状态,这很重要。下面是一种非常简单的方法,可以以最少的更改转换为迭代代码。

考虑这个递归代码:

struct tnode
{
    tnode(int n) : data(n), left(0), right(0) {}
    tnode *left, *right;
    int data;
};

void insertnode_recur(tnode *node, int num)
{
    if(node->data <= num)
    {
        if(node->right == NULL)
            node->right = new tnode(num);
        else
            insertnode(node->right, num);
    }
    else
    {
        if(node->left == NULL)
            node->left = new tnode(num);
        else
            insertnode(node->left, num);
    }    
}

迭代代码:

// Identify the stack variables that need to be preserved across stack 
// invocations, that is, across iterations and wrap them in an object
struct stackitem 
{ 
    stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
    tnode *node; int num;
    int ra; //to point of return
};

void insertnode_iter(tnode *node, int num) 
{
    vector<stackitem> v;
    //pushing a stackitem is equivalent to making a recursive call.
    v.push_back(stackitem(node, num));

    while(v.size()) 
    {
        // taking a modifiable reference to the stack item makes prepending 
        // 'si.' to auto variables in recursive logic suffice
        // e.g., instead of num, replace with si.num.
        stackitem &si = v.back(); 
        switch(si.ra)
        {
        // this jump simulates resuming execution after return from recursive 
        // call 
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {
                // replace a recursive call with below statements
                // (a) save return point, 
                // (b) push stack item with new stackitem, 
                // (c) continue statement to make loop pick up and start 
                //    processing new stack item, 
                // (d) a return point label
                // (e) optional semi-colon, if resume point is an end 
                // of a block.

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;         
            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {
                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;
            }
        }

        v.pop_back();
    }
}

请注意代码的结构如何仍然符合递归逻辑,并且修改最少,从而减少了错误数量。为了比较,我用 ++ 和 -- 标记了更改。除了 v.push_back 之外,大多数新插入的块对于任何转换的迭代逻辑都是通用的

void insertnode_iter(tnode *node, int num) 
{

+++++++++++++++++++++++++

    vector<stackitem> v;
    v.push_back(stackitem(node, num));

    while(v.size())
    {
        stackitem &si = v.back(); 
        switch(si.ra)
        {
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

------------------------

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;    

-------------------------

            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;

-------------------------

            }
        }

+++++++++++++++++++++++++

        v.pop_back();
    }

-------------------------

}
于 2013-04-29T14:43:54.607 回答
9

在谷歌上搜索“继续传递风格”。有一个转换为尾递归样式的通用过程;还有一个将尾递归函数转换为循环的通用过程。

于 2008-10-01T20:48:00.530 回答
6

只是消磨时间......递归函数

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

可以转换为

void foo(Node* node)
{
    if(node == NULL)
       return;

    // Do something with node...

    stack.push(node->right);
    stack.push(node->left);

    while(!stack.empty()) {
         node1 = stack.pop();
         if(node1 == NULL)
            continue;
         // Do something with node1...
         stack.push(node1->right);             
         stack.push(node1->left);
    }

}
于 2011-08-25T05:15:56.270 回答
6

想想实际上需要堆栈的东西:

如果我们将递归模式视为:

if(task can be done directly) {
    return result of doing task directly
} else {
    split task into two or more parts
    solve for each part (possibly by recursing)
    return result constructed by combining these solutions
}

例如,经典的河内塔

if(the number of discs to move is 1) {
    just move it
} else {
    move n-1 discs to the spare peg
    move the remaining disc to the target peg
    move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}

这可以转换为在显式堆栈上工作的循环,方法是将其重述为:

place seed task on stack
while stack is not empty 
   take a task off the stack
   if(task can be done directly) {
      Do it
   } else {
      Split task into two or more parts
      Place task to consolidate results on stack
      Place each task on stack
   }
}

对于河内塔,这变为:

stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
    task = stack.pop();
    if(task.size() = 1) {
        just move it
    } else {
        stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
        stack.push(new Task(1, task.from(), task.to(), task.spare()));
        stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
    }
}

关于如何定义堆栈,这里有相当大的灵活性。您可以使您的堆栈成为Command执行复杂操作的对象列表。或者你可以反其道而行之,让它成为一个更简单类型的列表(例如,一个“任务”可能是 4 个元素在堆栈中int,而不是在堆栈中的一个元素Task)。

这意味着堆栈的内存在堆中而不是在 Java 执行堆栈中,但这很有用,因为您可以更好地控制它。

于 2017-08-14T15:09:15.953 回答
5

通常,避免堆栈溢出的技术用于递归函数,称为蹦床技术,被 Java 开发人员广泛采用。

但是,对于 C#,这里有一个小辅助方法,可以将递归函数转换为迭代,而无需更改逻辑或使代码难以理解。C# 是一门很好的语言,用它可以创造出惊人的东西。

它通过帮助方法包装方法的一部分来工作。例如下面的递归函数:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

变成:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}
于 2012-05-23T11:31:20.593 回答
4

要寻找的一种模式是函数末尾的递归调用(所谓的尾递归)。这可以很容易地用一段时间来替换。例如,函数 foo:

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

以调用 foo 结束。这可以替换为:

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

这消除了第二次递归调用。

于 2008-10-01T20:48:55.600 回答
3

作为此问题的副本已关闭的问题具有非常具体的数据结构:

在此处输入图像描述

该节点具有以下结构:

typedef struct {
    int32_t type;
    int32_t valueint;
    double  valuedouble;
    struct  cNODE *next;
    struct  cNODE *prev;
    struct  cNODE *child;
} cNODE;

递归删除函数如下所示:

void cNODE_Delete(cNODE *c) {
    cNODE*next;
    while (c) {
        next=c->next;
        if (c->child) { 
          cNODE_Delete(c->child)
        }
        free(c);
        c=next;
    }
}

通常,对于多次调用自身(甚至一次)的递归函数,并不总是可以避免堆栈。但是,对于这种特殊的结构,这是可能的。这个想法是将所有节点展平为一个列表。这是通过将当前节点放在child顶行列表的末尾来完成的。

void cNODE_Delete (cNODE *c) {
    cNODE *tmp, *last = c;
    while (c) {
        while (last->next) {
            last = last->next;   /* find last */
        }
        if ((tmp = c->child)) {
            c->child = NULL;     /* append child to last */
            last->next = tmp;
            tmp->prev = last;
        }
        tmp = c->next;           /* remove current */
        free(c);
        c = tmp;
    }
}

这种技术可以应用于任何可以简化为具有确定性拓扑排序的 DAG 的数据链接结构。当前节点子节点被重新排列,以便最后一个子节点采用所有其他子节点。然后可以删除当前节点,然后遍历可以迭代到剩余的子节点。

于 2016-07-08T10:58:28.307 回答
2

递归只不过是从另一个函数调用一个函数的过程,只有这个过程是通过调用一个函数本身来完成的。正如我们所知,当一个函数调用另一个函数时,第一个函数保存其状态(其变量),然后将控制权传递给被调用函数。被调用的函数可以使用同名的变量来调用,例如 fun1(a) 可以调用 fun2(a)。当我们进行递归调用时,没有任何新的事情发生。一个函数通过将相同类型和名称相似的变量(但显然存储在变量中的值不同,只有名称保持不变)传递给自己来调用自己。但在每次调用之前,该函数都会保存其状态,并且此保存过程会继续进行。保存是在堆栈上完成的。

现在堆栈开始发挥作用。

因此,如果您编写一个迭代程序,每次都将状态保存在堆栈中,然后在需要时从堆栈中弹出值,那么您已经成功地将递归程序转换为迭代程序!

证明是简单和分析性的。

在递归中,计算机维护一个堆栈,而在迭代版本中,您将不得不手动维护堆栈。

考虑一下,只需将深度优先搜索(在图上)递归程序转换为 dfs 迭代程序。

祝一切顺利!

于 2012-05-18T10:06:16.303 回答
2

TLDR

您可以比较下面的源代码,前后对比以直观地理解该方法,而无需阅读整个答案。

我在处理非常大的文本块以生成后缀数组时遇到了一些多键快速排序代码的问题。由于所需的递归深度极深,代码将中止。通过这种方法,终止问题得到了解决。转换后,可以捕获某些作业所需的最大帧数,介于 10K 和 100K 之间,占用 1M 到 6M 内存。不是最佳解决方案,有更有效的方法来生成后缀数组。但无论如何,这是使用的方法。

该方法

将递归函数转换为适用于任何情况的迭代解决方案的一般方法是模仿在函数调用和调用返回期间本地编译的代码使用的过程。

举一个需要一些复杂方法的例子,我们有多键快速排序算法。这个函数有三个连续的递归调用,每次调用后,从下一行开始执行。

函数的状态被捕获在堆栈帧中,该堆栈帧被推入执行堆栈。当sort()从自身内部调用并返回时,将恢复调用时存在的堆栈帧。这样,所有变量都具有与调用之前相同的值 - 除非它们被调用修改。

递归函数

def sort(a: list_view, d: int):
    if len(a) <= 1:
        return
    p = pivot(a, d)
    i, j = partition(a, d, p)
    sort(a[0:i], d)
    sort(a[i:j], d + 1)
    sort(a[j:len(a)], d)

采用这个模型,并模仿它,一个列表被设置为堆栈。在此示例中,元组用于模拟帧。如果这是用 C 编码的,则可以使用结构。数据可以包含在数据结构中,而不是一次只推送一个值。

重新实现为“迭代”

# Assume `a` is view-like object where slices reference
# the same internal list of strings.

def sort(a: list_view):
    stack = []
    stack.append((LEFT, a, 0))                  # Initial frame.

    while len(stack) > 0:
        frame = stack.pop()  

        if len(frame[1]) <= 1:                  # Guard.
            continue

        stage = frame[0]                        # Where to jump to.

        if stage == LEFT: 
            _, a, d = frame                     # a - array/list, d - depth.
            p = pivot(a, d)
            i, j = partition(a, d, p)
            stack.append((MID, a, i, j, d))     # Where to go after "return".
            stack.append((LEFT, a[0:i], d))     # Simulate function call.

        elif stage == MID:                      # Picking up here after "call"
            _, a, i, j, d = frame               # State before "call" restored.
            stack.append((RIGHT, a, i, j, d))   # Set up for next "return".
            stack.append((LEFT, a[i:j], d + 1)) # Split list and "recurse".

        elif stage == RIGHT:
            _, a, _, j, d = frame
            stack.append((LEFT, a[j:len(a)], d)

        else:
           pass

进行函数调用时,函数返回后从何处开始执行的信息包含在堆栈帧中。在此示例中,if/elif/else块表示从调用返回后开始执行的点。在 C 中,这可以作为switch语句来实现。

在示例中,块被赋予标签;它们通过列表在每个块内的分区方式任意标记。第一个块“LEFT”在左侧拆分列表。“MID”部分表示在中间分割列表的块等。

使用这种方法,模仿呼叫需要两个步骤。首先,一帧被压入堆栈,这将导致在“调用”“返回”之后的当前块之后的块中继续执行。框架中的值指示if/elif/else在“调用”之后的循环中落入哪个部分。

然后“调用”帧被压入堆栈。对于此特定示例,在大多数情况下,这会将执行发送到第一个“LEFT”块。这是实际排序完成的地方,无论列表的哪个部分被拆分到那里。

在循环开始之前,推到函数顶部的主帧代表初始调用。然后在每次迭代中,都会弹出一个帧。框架中的“LEFT/MID/RIGHT”值/标签用于落入if/elif/else语句的正确块中。该帧用于恢复当前操作所需变量的状态,然后在下一次迭代中弹出返回帧,将执行发送到后续部分。

返回值

如果递归函数返回一个自己使用的值,则可以像对待其他变量一样对待它。只需在堆栈帧中为其创建一个字段。如果“被调用者”正在返回一个值,它会检查堆栈以查看它是否有任何条目;如果是这样,则更新堆栈顶部框架中的返回值。对于这个例子,你可以检查这个相同方法的另一个例子,以递归到迭代转换。

结论

像这样将递归函数转换为迭代函数的方法本质上也是“递归的”。代替进程堆栈用于实际的函数调用,另一个以编程方式实现的堆栈取而代之。

得到了什么?也许在速度上有一些边际改进。或者它可以作为一种绕过某些编译器和/或执行环境(堆栈指针命中保护页)施加的堆栈限制的方法。在某些情况下,可以减少压入堆栈的数据量。增益是否通过模仿我们通过递归实现自动获得的东西来抵消代码中引入的复杂性?

在排序算法的情况下,找到一种方法来实现这个特定的没有堆栈的算法可能具有挑战性,而且有很多迭代排序算法可用,而且速度要快得多。据说任何递归算法都可以迭代实现。当然......但是有些算法在没有被修改到不再是同一个算法的情况下不能很好地转换。

仅仅为了转换递归算法而转换它们可能不是一个好主意。无论如何,对于它的价值,上述方法是一种通用的转换方式,应该适用于几乎任何事情。

如果你发现你真的需要一个迭代版本的递归函数,它不使用自己的内存消耗堆栈,最好的方法可能是废弃代码并使用学术文章中的描述编写你自己的代码,或者工作它写在纸上,然后从头开始编码,或者其他从头开始的方法。

于 2021-08-21T12:20:59.143 回答
1

有一种通用的方法可以通过使用连接多个迭代器供应商的惰性迭代器(返回迭代器的 lambda 表达式)将递归遍历转换为迭代器。请参阅我的将递归遍历转换为迭代器

于 2017-11-14T04:45:56.847 回答
1

使用堆栈将递归函数转换为迭代函数的另一个简单而完整的示例。

#include <iostream>
#include <stack>
using namespace std;

int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }

struct Par
{
    int a, b;
    Par() : Par(0, 0) {}
    Par(int _a, int _b) : a(_a), b(_b) {}
};

int GCDIter(int a, int b)
{
    stack<Par> rcstack;

    if (b == 0)
        return a;
    rcstack.push(Par(b, a % b));

    Par p;
    while (!rcstack.empty()) 
    {
        p = rcstack.top();
        rcstack.pop();
        if (p.b == 0)
            continue;
        rcstack.push(Par(p.b, p.a % p.b));
    }

    return p.a;
}

int main()
{
    //cout << GCD(24, 36) << endl;
    cout << GCDIter(81, 36) << endl;

    cin.get();
    return 0;
}
于 2018-06-14T12:03:13.273 回答
1

我的示例在 Clojure 中,但应该很容易翻译成任何语言。

鉴于此函数StackOverflows 用于较大的 n 值:

(defn factorial [n]
  (if (< n 2)
    1
    (*' n (factorial (dec n)))))

我们可以通过以下方式定义使用自己的堆栈的版本:

(defn factorial [n]
  (loop [n n
         stack []]
    (if (< n 2)
      (return 1 stack)
      ;; else loop with new values
      (recur (dec n)
             ;; push function onto stack
             (cons (fn [n-1!]
                     (*' n n-1!))
                   stack)))))

其中return定义为:

(defn return
  [v stack]
  (reduce (fn [acc f]
            (f acc))
          v
          stack))

这也适用于更复杂的函数,例如ackermann 函数

(defn ackermann [m n]
  (cond
    (zero? m)
    (inc n)

    (zero? n)
    (recur (dec m) 1)

    :else
    (recur (dec m)
           (ackermann m (dec n)))))

可以转化为:

(defn ackermann [m n]
  (loop [m m
         n n
         stack []]
    (cond
      (zero? m)
      (return (inc n) stack)

      (zero? n)
      (recur (dec m) 1 stack)

      :else
      (recur m
             (dec n)
             (cons #(ackermann (dec m) %)
                   stack)))))
于 2020-04-28T06:20:09.950 回答
0

系统如何使用任何递归函数并使用堆栈执行它的粗略描述:

这是为了展示这个想法而没有细节。考虑这个将打印出图形节点的函数:

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

例如图表: A->B A->C show(A) 将打印 B, A, C

函数调用意味着保存本地状态和延续点,以便您可以返回,然后跳转您要调用的函数。

例如,假设 show(A) 开始运行。第 3 行的函数调用。 show(B) 意味着 - 将项目添加到堆栈,意思是“您需要在第 2 行继续,局部变量状态节点 = A” - 转到第 0 行,节点 = B。

为了执行代码,系统运行指令。当遇到函数调用时,系统将需要返回的信息推送到原来的位置,运行函数代码,当函数完成时,弹出关于需要去哪里继续的信息。

于 2013-08-02T21:08:41.573 回答
0

链接提供了一些解释,并提出了保持“位置”以便能够在几个递归调用之间到达确切位置的想法:

但是,所有这些示例都描述了递归调用执行固定次数的场景。当您遇到以下情况时,事情会变得更加棘手:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}
于 2014-11-30T04:56:56.487 回答
0

这是一个老问题,但我想添加一个不同的方面作为解决方案。我目前正在做一个项目,在这个项目中我使用了 C# 的洪水填充算法。通常,我一开始使用递归来实现这个算法,但很明显,它导致了堆栈溢出。之后,我将方法从递归更改为迭代。是的,它起作用了,我不再收到堆栈溢出错误。但这一次,由于我将洪水填充方法应用于非常大的结构,因此程序进入了无限循环。出于这个原因,我想到这个函数可能重新进入了它已经访问过的地方。作为对此的最终解决方案,我决定为访问点使用字典。如果该 node(x,y) 已经第一次添加到堆栈结构中,则该 node(x, y) 将作为键保存在字典中。即使稍后尝试再次添加相同的节点,它也不会被添加到堆栈结构中,因为该节点已经在字典中。让我们看看伪代码:

startNode = pos(x,y)

Stack stack = new Stack();

Dictionary visited<pos, bool> = new Dictionary();

stack.Push(startNode);

while(stack.count != 0){
    currentNode = stack.Pop();
    if "check currentNode if not available"
        continue;
    if "check if already handled"
        continue;
    else if "run if it must be wanted thing should be handled"      
        // make something with pos currentNode.X and currentNode.X  
        
        // then add its neighbor nodes to the stack to iterate
        // but at first check if it has already been visited.
        
        if(!visited.Contains(pos(x-1,y)))
            visited[pos(x-1,y)] = true;
            stack.Push(pos(x-1,y));
        if(!visited.Contains(pos(x+1,y)))
            ...
        if(!visited.Contains(pos(x,y+1)))
            ...
        if(!visited.Contains(pos(x,y-1)))
            ...
}

于 2021-07-01T11:03:05.510 回答