迭代轉換的遞歸

我試圖將我的代碼從遞歸函數重新編寫成迭代函數時遇到困難。迭代轉換的遞歸

我想我會問是否有任何一般的事情要考慮/技巧/指導等......關於從遞歸代碼到迭代代碼。

例如我不能真正理解如何獲得下面的代碼迭代，主要是由於遞歸內部的循環，這進一步依賴於並且調用下一個遞歸。

struct entry 
{ 
    uint8_t values[8]; 
    int32_t num_values; 
    std::array<entry, 256>* next_table; 

    void push_back(uint8_t value) {values[num_values++] = value;} 
}; 

struct node 
{ 
    node*    children; // +0 right, +1 left 
    uint8_t    value; 
    uint8_t    is_leaf; 
}; 

void build_tables(node* root, std::array<std::array<entry, 8>, 255>& tables, int& table_count) 
{ 
    int table_index = root->value; // root is always a non-leave, thus value is the current table index. 

    for(int n = 0; n < 256; ++n) 
    { 
     auto current = root; 

     // Recurse the the huffman tree bit by bit for this table entry 
     for(int i = 0; i < 8; ++i) 
     { 
      current = current->children + ((n >> i) & 1); // Travel to the next node current->children[0] is left child and current->children[1] is right child. If current is a leaf then current->childen[0/1] point to the root. 
      if(current->is_leaf) 
       tables[table_index][n].push_back(current->value); 
     } 

     if(!current->is_leaf) 
     { 
      if(current->value == 0) // For non-leaves, the "value" is the sub-table index for this particular non-leave node 
      { 
       current->value = table_count++; 
       build_tables(current, tables, table_count); 
      } 

      tables[table_index][n].next_table = &tables[current->value]; 
     } 
     else 
      tables[table_index][n].next_table = &tables[0]; 
    } 
}

來源

2011-08-30 ronag

考慮這個問題:(可能重複？）http://stackoverflow.com/questions/1549943/design-patterns-for-converting-recursive-algorithms-to-iterative-ones – Nathan

偉大的聯繫！謝謝，我以前在尋找時沒有找到它。我意識到std :: stack的做法。然而，我似乎有點困惑的事實，我有一個循環內我的遞歸下一個遞歸依賴，不知道如何處理？ – ronag

這會鼓勵我回答，如果你提供了關於代碼的解釋，我沒有時間去嘗試弄清楚自己。編輯：遞歸內部的循環將變成循環內的循環。 –

由於tables和table_count始終指向同一個對象，你可以通過它們存儲爲臨時結構成員，然後做一些事情做一個小的性能提升，採取tables和table_count出build_tables參數列表像這樣：

struct build_tables_struct 
{ 
    build_tables_struct(std::array<std::array<entry, 8>, 255>& tables, int& table_count) : 
    tables(tables), table_count(table_count) {} 
    std::array<std::array<entry, 8>, 255>& tables; 
    int& table_count; 
    build_tables_worker(node* root) 
    { 
    ... 
    build_tables_worker(current); // instead of build_tables(current, tables, table_count); 
    ... 
    } 
} 

void build_tables(node* root, std::array<std::array<entry, 8>, 255>& tables, int& table_count) 
{ 
    build_tables_struct(tables, table_count).build_tables_worker(root); 
}

這適用當然只是如果你的編譯器是不是足夠聰明，使這種優化本身。

否則，您可以使此非遞歸的唯一方法是自己管理堆棧。我懷疑這會比遞歸版本更快。

這一切被說，我懷疑你的性能問題在這裏是遞歸。將三個引用參數推入堆棧並調用一個函數與您的函數所做的工作相比，我認爲這不是一個巨大的負擔。

來源

2011-08-31 01:27:15 Clinton

迭代轉換的遞歸

回答

相關問題