Recursive to Iterative Transformation

I've gotten stuck on trying to re-write my code from a recursive function into an iterative function.

I thought I'd ask if there are any general things to think about/tricks/guidelines etc... in regards to going from recursive code to iterative code.

e.g. I can't rly get my head around how to get the following code iterative, mainly due to the loop inside the recursion which further depends on and calls the next recursion.

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

---

As tables and table_count always refer to the same objects, you might make a small performance gain by taking tables and table_count out of the argument list of build_tables by storing them as members of a temporary struct and then doing something like this:

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

This applies of course only if your compiler is not smart enough to make this optimisation itself.

The only way you can make this non-recursive otherwise is managing the stack yourself. I doubt this would be much if any faster than the recursive version.

This all being said, I doubt your performance issue here is recursion. Pushing three reference arguments to the stack and calling a function I don't think is a huge burden compared to the work your function does.