1

一些伪代码：

 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 之下。

如何将其更改为迭代？

4

2 回答 2

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

留作练习：更改迭代，以便您可以将当前迭代的集合 (from 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;
}
于 2013-04-22T16:39:49.090 回答
0

您可以通过添加一个防止您双重处理x值的保护来保留递归版本（没有堆栈溢出）

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

如果您的某些数组值可能已初始化为 1，则将其更改为类似

if(p[x] != null) {
    p[x] = null;

即分配一个您知道未在初始数组中使用的值。然后当函数完成其处理时，遍历数组并将所有空值设置为 1。

于 2013-04-22T16:06:55.137 回答