從遞歸更改此進行迭代

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