algorithm - 将其从递归更改为迭代

Question

一些伪代码:

 func F(int x. int y, array p){
       p[x] = 1;
       if (x<=y){
          for each item in getItems(x,p){
              p = F(item,y,p);
          }
       }
       return p;
    }

getItems() 返回一个基于 x 和 p 的数字数组，对于这个问题来说并不重要，但它会返回一些高于和低于 x 的数字。然而，这意味着如果 x 太大，那么我会炸毁递归堆栈，因为它会深入到 x 以下。

如何将其更改为迭代？

Answer 1

您可以通过模拟调用堆栈来实现:

struct stackentry {
    int x;
    Item item; // see exercise for reader, below
};

func F(int x, int y, array p){
   dynamic_list_of_stackentry mystack;
  start:
   p[x] = 1;
   if (x<=y){
      for each item in getItems(x,p){
          mystack.push(stackentry(x, item));
          x = item
          goto start
        resume:
          x = mystack.top().x;
          item = mystack.top().item;
          mystack.pop();
      }
   }
   if mystack.size() > 0:
      goto resume
   return p;
}

留作练习:更改迭代，以便您可以将当前正在迭代的集合(来自 getItems())和您的当前位置存储为堆栈条目的一部分

我并不是说这是优雅的代码，但您可以从非递归函数的这个起点重构，它与您的递归函数具有相同的功能。例如，您的下一步可能是:

func F(int x, int y, array p){
   dynamic_list_of_int mystack;
   mystack.push(x)
   while not mystack.empty() {
       x = mystack.top();
       mystack.pop();
       p[x] = 1;
       if (x <= y) {
           for each item in reversed(getItems(x,p)) {
               mystack.push(item);
           }
       }
   }
   return p;
}