c++ - 如何推广这种方法(堆上的递归模拟)
问题描述
在学校进行回溯时,我偶然发现了一个个人项目,在该项目中我必须用递归函数做大迷宫。我坚持了一下,想出了一种将递归函数转换为迭代函数同时仍保持递归行为的方法。我也知道我可以用更多的堆栈内存来编译项目,但我试图实现的将大大增加递归函数的深度。(深度现在取决于程序可以分配多少堆而不是堆栈)
这是说明此方法的最简单示例:
// 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;
}
现在我用这种替换递归函数的方法遇到的问题是它们太让人头疼了。这是一个简单的 2 行函数转换为 40 行函数。我希望能够制作类似于标题的东西,这将减少我每次想要使用它时需要编写的代码行,但我不知道如何开始。
解决方案
我减少到 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;
}
推荐阅读
- ruby - 将 Array 与哈希项一起使用
- swift4 - UIActivityViewController Facebook 分享 URL + IMAGE 和 URL + TEXT 不起作用
- java - 在 Java 中为 GC 与 WeakReference 设置空对象
- c++ - 有没有像 BigInteger 这样的变量,但作为浮点数?
- solr - SolrCloud 异常将文档 id 写入索引;可能的分析错误
- abap - 未从 EQUI 中选择记录
- javascript - Realm.js 查询字符串属性列表
- ruby-on-rails - Javascript:Firefox 中显示的日期无效
- python - 关闭交互式 python 会话时结束非守护线程
- ios - UITableView 单元格折叠动画看起来很糟糕