内存分配的递归
Recursion With Memory Allocation
我正在观看有关 CUDA 和 Barnes-Hut 算法的视频，其中指出有必要对 GPU 的树设置深度限制，然后我突然想到可能进行递归在堆中。
基本上，我想知道的是：是否可以从堆中分配内存并将其用作临时 "stack" 在其中放置对相关递归函数的函数调用以稍微延迟堆栈溢出？
如果是，如何实现，我们是否分配space作为函数指针？我假设它会涉及在堆中存储函数地址，但我不太确定。
[edit] 我只是想补充一点，这纯粹是一个理论问题，我想这样做会导致程序在使用堆后变慢。
[edit] 根据要求，我使用的编译器是 Ubuntu 14.04（64 位）
上的 GCC 4.8.4
当然可以。这称为连续传递样式。标准库通过 setjmp() 和 longjmp() 支持它，并将控制权恢复到名为 jmp_buf 的结构中的较早点所需的信息。 （对于从哪里恢复有几个限制。）你可以将它们存储在一个堆栈中，这只是一个后进先出队列。
一种更通用的方法是 运行 将程序作为状态机，并将回溯程序状态所需的信息（称为延续）存储在称为蹦床的数据结构中。想要这样做的一个常见原因是在没有优化它的实现中获得尾递归的等价物，并且可能会消耗大量堆栈 space。我认识的人目前正在编写一个 trampoline 的一个真实世界的应用程序是一个 GLL 解析器，其中语法表示为有向图，解析的结果是一个共享的压缩解析林，解析器通常需要回溯以尝试不同的规则。
Continuation-passing 和 trampolines 似乎被认为是花哨的风格，因为它们来自函数式编程的世界，而 longjmp() 被认为是丑陋的低级黑客，甚至 Linux手册页说不要使用它。
您可以通过将您自己的基于堆的堆栈实现为结构数组来模拟这一点，每个结构代表一个堆栈帧，其中包含等效的参数和局部变量。该函数不是递归地调用自身，而是循环并且每个 "call" 显式地将一个新帧推入堆栈。
几年前，我在尝试解决一个简单的棋盘游戏时正是这样做的。程序本来就是递归的，一直拖到运行。我把它改成上面的结构，这使得制作应用程序变得简单interruptible/restartable。当中断时，应用程序将其 "stack" 转储到状态文件。重新启动时，应用会加载状态文件并从中断处继续。
如果堆栈帧结构包含嵌入式指针，这确实需要一些注意，但这并非不可逾越。
我正在观看有关 CUDA 和 Barnes-Hut 算法的视频，其中指出有必要对 GPU 的树设置深度限制，然后我突然想到可能进行递归在堆中。
基本上，我想知道的是：是否可以从堆中分配内存并将其用作临时 "stack" 在其中放置对相关递归函数的函数调用以稍微延迟堆栈溢出？
如果是，如何实现，我们是否分配space作为函数指针？我假设它会涉及在堆中存储函数地址，但我不太确定。
[edit] 我只是想补充一点，这纯粹是一个理论问题，我想这样做会导致程序在使用堆后变慢。
[edit] 根据要求，我使用的编译器是 Ubuntu 14.04（64 位）
上的 GCC 4.8.4当然可以。这称为连续传递样式。标准库通过 setjmp() 和 longjmp() 支持它，并将控制权恢复到名为 jmp_buf 的结构中的较早点所需的信息。 （对于从哪里恢复有几个限制。）你可以将它们存储在一个堆栈中，这只是一个后进先出队列。
一种更通用的方法是 运行 将程序作为状态机，并将回溯程序状态所需的信息（称为延续）存储在称为蹦床的数据结构中。想要这样做的一个常见原因是在没有优化它的实现中获得尾递归的等价物，并且可能会消耗大量堆栈 space。我认识的人目前正在编写一个 trampoline 的一个真实世界的应用程序是一个 GLL 解析器，其中语法表示为有向图，解析的结果是一个共享的压缩解析林，解析器通常需要回溯以尝试不同的规则。
Continuation-passing 和 trampolines 似乎被认为是花哨的风格，因为它们来自函数式编程的世界，而 longjmp() 被认为是丑陋的低级黑客，甚至 Linux手册页说不要使用它。
您可以通过将您自己的基于堆的堆栈实现为结构数组来模拟这一点，每个结构代表一个堆栈帧，其中包含等效的参数和局部变量。该函数不是递归地调用自身，而是循环并且每个 "call" 显式地将一个新帧推入堆栈。
几年前，我在尝试解决一个简单的棋盘游戏时正是这样做的。程序本来就是递归的，一直拖到运行。我把它改成上面的结构，这使得制作应用程序变得简单interruptible/restartable。当中断时，应用程序将其 "stack" 转储到状态文件。重新启动时，应用会加载状态文件并从中断处继续。
如果堆栈帧结构包含嵌入式指针，这确实需要一些注意，但这并非不可逾越。