我正在观看一个关于 CUDA 和 Barnes-Hut 算法的视频,其中指出有必要对 GPU 的树设置深度限制,然后我的脑海中突然冒出一个想法,即可能在堆。
基本上,我想知道的是:是否可以从堆中分配内存并将其用作临时“堆栈”,在其中放置对相关递归函数的函数调用以在一定程度上延迟堆栈溢出?
如果是这样,它如何实现,我们是否会为指向函数的指针分配空间?我假设它会涉及在堆中存储函数地址,但我不太确定。
[edit] 我只是想补充一点,这纯粹是一个理论问题,我想这样做会导致程序在使用堆后变慢。
[编辑] 根据要求,我使用的编译器是 Ubuntu 14.04(64 位)上的 GCC 4.8.4
最佳答案
当然。这称为连续传递样式。标准库支持 setjmp()
和 longjmp()
, 并将控制权恢复到先前点所需的信息存储在名为 jmp_buf
的结构中. (对于可以从哪里恢复有几个限制。)您可以将它们存储在堆栈中,这只是一个后进先出队列。
一种更通用的方法是将程序作为状态机运行,并将回溯程序状态所需的信息(称为延续)存储在称为蹦床的数据结构中。想要这样做的一个常见原因是在不优化尾递归的实现中获得等价物,并且可能会占用大量堆栈空间。我认识的人目前正在编写一个 trampoline 的一个真实世界的应用程序是一个 GLL 解析器,其中语法表示为有向图,解析的结果是一个共享的压缩解析林,解析器通常需要回溯以尝试不同的规则。
Continuation-passing 和 trampolines 似乎被认为是花哨的风格,因为它们来自函数式编程的世界,而 longjmp()
被认为是一种丑陋的低级 hack,甚至 Linux 手册页都说不要使用它。
关于c - 内存分配的递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32995943/