Рекурсивно к итеративному преобразованию

Question

Я застрял при попытке переписать мой код из рекурсивной функции в итеративную функцию.

Я подумал, что могу спросить, есть ли какие-нибудь общие соображения по поводу / хитрости / руководств и т. Д. В отношении перехода от рекурсивного кода к итеративному коду.

например. Я не могу понять, как сделать следующий код итеративным, в основном из-за цикла внутри рекурсии, который далее зависит от следующей рекурсии и вызывает ее.

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

Answer 1

Поскольку 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);
}

Это применимо, конечно, только если ваш компилятор недостаточно умен, чтобы выполнить эту оптимизацию самостоятельно.

Единственный способ сделать это нерекурсивным - это управлять стеком самостоятельно. Я сомневаюсь, что это будет намного быстрее, чем рекурсивная версия.

При всем этом я сомневаюсь, что ваша проблема с производительностью здесь - это рекурсия. Передача трех ссылочных аргументов в стек и вызов функции, которую я не считаю большой нагрузкой по сравнению с работой, выполняемой вашей функцией.