从递归更改此进行迭代

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和对数字数组，并且不是对这个问题的缘故重要，但它返回几高于和低于x的数字。然而，这意味着如果x太大，那么我会炸毁递归堆栈，因为它会深入到x以下。

我怎样才能改变这个迭代？

Answer 1

您可能能够通过增加保护，防止您从双处理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

Answer 2

你可以做到这一点通过模拟调用堆栈：

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