递归与内存分配

Question

我在看有关CUDA和Barnes-Hut算法的视频时，其中提到必须对GPU树设置深度限制。这使我想到了在堆中进行递归的可能性。

我的问题是：是否可以从堆中分配内存，并将其用作临时“堆栈”，以便将递归函数的函数调用放入其中，以延迟堆栈溢出？

如果可以，如何实现？我们是否应该为指向函数的指针分配空间？我认为这可能涉及将函数地址存储在堆中，但我不确定。

[编辑] 我只想补充说，这纯粹是一个理论问题，我想象中这样做会导致程序一旦使用堆就变慢。

[编辑] 根据要求，我使用的编译器是Ubuntu 14.04（64位）上的GCC 4.8.4。

- Plopperzz

---

C语言并未定义任何此类机制。事实上，它根本没有用这些或任何其他名称定义"stack"或"heap"。它们是大多数实现的标准名称，但它们超出了C的范围。一方面，这意味着您需要指定特定的实现才能获得有用的答案。另一方面，这也意味着C本身并不禁止您所描述的内容。另外，我不知道是否有任何实现提供它。 - John Bollinger

@JohnBollinger 对不起，我不太明白你说的需要指定特定实现是什么意思。你是指语言本身如何处理内存吗？到目前为止，我只学了一些入门课程，除了C编译器（我猜大多数编译器）如何管理内存的基础知识外，还没有涉及到这方面的内容。 - Plopperzz

“指定特定的实现”意味着将问题的范围缩小到类似于Linux上的GCC 5 / glibc或Windows 10上的MS Visual C ++ 2013这样的东西。 - John Bollinger

@JohnBollinger 已完成，谢谢，我没有想到那个。 - Plopperzz

Answer 1

当然。这被称为续传风格（continuation-passing style）。标准库使用setjmp()和longjmp()支持它，并将恢复控制到较早点所需的信息存储在结构体jmp_buf中。（有几个限制需要注意，例如无法从任意位置进行恢复。）您需要将它们存储在一个栈中，这只是一个后进先出队列。

更一般的方法是将程序作为状态机运行，并将用于回溯程序状态的信息（称为continuation）存储在名为trampoline的数据结构中。常见的原因是在不优化尾递归的实现中获得其等效效果，该实现可能会占用大量堆栈空间。一个真实世界的应用程序是一个GLL解析器，其中语法被表示为定向图形，解析的结果是共享的紧缩解析森林，解析器经常需要回溯以尝试不同的规则。

Continuation-passing和Trampolines似乎被认为是花式编程，因为它们来自函数式编程领域，而longjmp()被认为是一个丑陋的低级黑客技巧，甚至Linux手册也建议不要使用它。

- Davislor

---

我认为continuations并没有真正解决所提出的问题，因为它们既不会改变系统在后续调用中使用的堆栈，也不会改变直接代码或连续体中的堆栈。然而，在需要连续体的情况下，重要的是要注意setjmp()/longjmp()仅以有限的方式支持它们，一旦控制权离开调用了setjmp()的函数，相应longjmp的行为就不再被定义。 - John Bollinger

这是一个与函数调用和返回不同的控制流替代手段。话虽如此，您关于 longjmp() 的评论并不正确：如果原始函数已经退出，则行为未定义，而不是控制离开它。从被调用了 setjmp() 的函数递归调用 longjmp() 是合法的。事实上，这就是 goto 不足以解决的用例。 - Davislor

“控制权离开”实际上是指函数通过调用longjmp()返回或退出，而不是调用（其他）函数。无论如何，OP的问题特别涉及在调用堆栈中使用不同的内存区域。鉴于续延是调用/返回的替代方案，因此它们并不能解决这个问题。 - John Bollinger

@JohnBollinger 我不同意。问题是，“是否可以从堆中分配内存，并将其用作临时“堆栈”，以便将函数调用放入递归函数中…？”我在第二段中讨论的跳板正是这样做的。传递续体与之密切相关且等效，特别是在用于实现尾递归时。这是实现OP想要的常见方法，因此我认为指向那个方向会有所帮助。 - Davislor

Answer 2

您可以通过实现自己的基于堆的栈作为结构体数组来模拟这一过程，每个结构体代表一个包含参数和本地变量等价物的堆栈帧。函数不再递归调用自身，而是循环执行，每次“调用”都会显式地将一个新帧推入堆栈中。

多年前，我在尝试解决一个简单的棋盘游戏时就这样做了。程序最初是递归的，运行时间非常长。我将其改为上述结构，这使得应用程序易于中断/重新启动。当应用程序被中断时，它会将其“堆栈”转储到状态文件中。重新启动时，应用程序加载状态文件并继续之前的工作。

如果堆栈帧结构包含嵌入指针，则需要特别小心处理，但这并非难以克服。

- keithmo