Как обобщить этот подход (симуляция рекурсии в куче)

Question

Когда я возвращался в школу, я наткнулся на личный проект, в котором мне пришлось делать большие лабиринты с рекурсивной функцией.Я немного подумал и придумал способ преобразования рекурсивной функции в итеративную функцию , сохраняя при этом рекурсивное поведение .Я также осознаю тот факт, что я могу скомпилировать проект с большим количеством стековой памяти, но то, что я пытаюсь реализовать, значительно увеличит глубину рекурсивной функции.(глубина теперь будет зависеть от того, сколько кучи может выделить программа, а не стек)

Это самый простой пример, иллюстрирующий этот метод:

// An adaptation of the Gauss sum calculated with a recursive function.
// I know this is primitive recursion but i just want to make the approach clear.

//Here is the normal way of writing a Gauss sum recursive function
unsigned long long GaussStack (unsigned long long n)
{
    if (n == 0) return 0;
    return n + GaussStack(n-1);
}

//And this is the adaptation of the "heap" recursion Gauss sum function.
//Brief explination:  
//  I am creating a double chained list (on the heap) which will imitate the
//   stack. Each element will hold the return_value and the parameter n.

unsigned long long GaussHeap(unsigned long long x)
{
    struct INSTANCE
    {
        unsigned long long x;
        unsigned long long return_value;
        INSTANCE* next;
        INSTANCE* prev;
    };

    INSTANCE* FIRST_CALL = new INSTANCE;
    INSTANCE* THIS_CALL = FIRST_CALL; // NOT TO BE CONFUSED with the __thiscall calling convention

    // We initialize the first simulated call
    FIRST_CALL->x = x;
    FIRST_CALL->return_value = 0; // optional in this case
    FIRST_CALL->prev = NULL;      // optional in this case

    //And now the hard thing comes.
    //No matter what recursive function you try to aproach with this method,
    // it will split the code into parts defined by labels.
    //Where the code is split depends on where the recursive call
    // is placed inside the function definition.
    //One function can be separated into more parts.
    // (don't even want to imagine how ackermann will look)
    //This example is similar to the __cdecl method of allocating space for
    // a function instance.


    label_NewCall:
        // Here we test the stopping condition
        if (THIS_CALL->x == 0)
        {
            THIS_CALL->return_value = 0;
            goto label_EndCall;
        }

        // Here we allocate the space for the next instance
        THIS_CALL->next = new INSTANCE;

        // "pass" the parameter
        THIS_CALL->next->x = THIS_CALL->x - 1;

        // Link the next instance to this instance
        THIS_CALL->next->prev = THIS_CALL;

        THIS_CALL = THIS_CALL->next;
     goto label_NewCall;

     // If you compare this function with the normal function
     // this gap between labels is represented by the "GaussStack(n-1)" call.

     label_EndCall:
         // We go back to the previous call
         THIS_CALL = THIS_CALL->prev;

         // "Collect" the return value
         THIS_CALL->return_value = THIS_CALL->x + THIS_CALL->next->return_value;

         // Delete the space allocated for that call
         delete THIS_CALL->next;

     if(THIS_CALL != FIRST_CALL) goto label_EndCall;

     // Now we can just do :
     return FIRST_CALL->return_value;
     // But we will leave on the heap the FIRST_CALL space
     // so we will have to create a new static variable or use one that is already
     // declared to save the return_value before deleting FIRST_CALL

     // We can do :
     unsigned long long var = THIS_CALL->return_value;
     delete THIS_CALL;
     return var;

     // Or because we already have x declared as THE SAME DATA TYPE as THE
     // RETURN VALUE OF THE FUNCTION, we can do : 
     x = THIS_CALL->return_value;
     delete THIS_CALL;
     return x;  
}


int main()
{
    // The normal GaussStack() function fails between 40,000 and 50,000 at 1MB Stack.
    std::cout << GaussStack(40000) << '\n'; 
    // While the GaussHeap() will hold on before throwing bad_alloc until
    // 50,000,000 at almost 2GB Heap.
    std::cout << GaussHeap(50000000) << '\n';
    return 0;
}

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

Answer 1

Я сократил до 23 строк (включая определение struct), но все еще вполне читабелен:

#include <memory>

template<typename T> struct inst_t
{
    using inst_ptr = std::unique_ptr<inst_t<T>>;
    T n{}, res{};
    inst_t* prev{};
    inst_ptr next{};

    inst_t (T n, T res = T{}, inst_t *prev = nullptr, inst_ptr &&next = nullptr)
        : n{ n }, res{ res }, prev{ prev }, next{ std::move(next) } {};
};

template<typename T> T GaussHeap(T n)
{
    auto first{ std::make_unique<inst_t<T>>(n) };
    auto now = first.get();
//         .............  condition that breaks the "recursion"
    for (; now->n != T{}; now = now->next.get())
        now->next = std::make_unique<inst_t<T>>(now->n-1, T{}, now);
//                                              ^^^^^^^^ place argument for next call here
    for (; now != first.get(); now->res = now->n + now->next->res)
        now = now->prev;    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                            //   and collection of results here
    return first->res;
}

Answer 2

То, что вы делаете там, это моделирование стека со связанным списком.Вместо этого вы можете просто использовать std::stack, который позаботится о вас.Вызовите push, чтобы положить что-то в стек, и pop, чтобы удалить это.Эти две операции соответствуют добавлению и удалению узлов в начале связанного списка.

std::stack размещает свой резервный массив в куче.