Recursive to Iterative Transformation

Question

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

Consider this question: (Possible duplicate?) http://stackoverflow.com/questions/1549943/design-patterns-for-converting-recursive-algorithms-to-iterative-ones — Nathan, Aug 30 '11 at 19:40
Great link! Thank you, didn't find it when I was searching before. I was aware of the std::stack way of doing it. However, I seem to get a bit confused by the fact that I have a loop inside my recursion that the next recursion depends on, not sure how to handle that? — ronag, Aug 30 '11 at 20:03
It would encourage me to answer if you provided an explanation of what the code does, I don't have the time to try to figure it out myself. Edit: a loop inside a recursion would turn into a loop inside a loop. — Seth Carnegie, Aug 30 '11 at 20:03
I'm building a table for huffman decoding (google: "efficient huffman decoding"). So the "node" structure is a huffman tree, from which I wish to generate the decoding table. — ronag, Aug 30 '11 at 20:08
It would probably help to show how the `node` struct is defined. — Dawson, Aug 30 '11 at 20:13
people ask about huffman encoding a lot too, ie: http://stackoverflow.com/questions/5440094/what-is-the-most-efficient-of-building-a-canonical-huffman-tree — Tom Kerr, Aug 30 '11 at 21:34
I've got the enture huffman coding functionality working. It just that this particular code is slow due to its recursion, which is why I would like to rewrite it. — ronag, Aug 30 '11 at 22:17
It was simple to solve, dunno why I got stuck on it, please vote for close as it's a duplicate of what was mentioned in the first link. — ronag, Aug 30 '11 at 22:22

score 1 · Accepted Answer · answered Aug 31 '11 at 01:27

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.

Recursive to Iterative Transformation

1 Answers1