仅使用堆区域的递归
是否有仅使用堆区域的递归示例？
Are there examples of recursion using only heap area?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
是否有仅使用堆区域的递归示例？
Are there examples of recursion using only heap area?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（6）
在 C 中，基于函数调用的递归总是使用堆栈，几乎按照定义。
如果您愿意将递归转换为迭代，那么可以仅使用堆空间，但这并不是真正的递归。您可以通过在堆中实现堆栈来实现这一点。
某些问题可以使用尾递归，它会重复覆盖堆栈的同一区域。
In C, function call-based recursion always uses the stack, almost by definition.
If you are willing to convert your recursion to iteration, then it is possible to use only heap space, but that isn't really recursion. You would do so by implementing a stack in the heap.
Certain problems can use tail recursion, which repeatedly overwrites the same area of the stack.
您可以做一些疯狂的事情，例如 malloc 一个新区域，关闭中断和几乎所有其他操作（在许多系统上不可能）并将堆栈指针设置为该 malloc 区域。从技术上讲，您仍在使用堆栈，但该堆栈位置现在位于堆上。这不是一个好主意，但它可以在您具有这种控制级别的某些嵌入式类型系统上工作。
You could do something crazy like malloc a new area, turn off interrupts and just about everything else (not possible on many systems) and set your stack pointer to that malloc area. You are technically still playing with a stack, but that stack location is now on the heap. Not a good idea to do, but it can work on some embedded type systems where you have this level of control.
为了使函数递归，它必须至少调用自身一次。当它调用自身时，它会在堆栈上放置一个指向自身的指针，以供递归调用返回。当然，堆栈不是堆，因此仅使用堆的递归函数是不可能的。
（至少，在 C 中不是这样。函数式语言经过优化，可重复使用堆栈空间，并且不会为返回调用分配指针）
In order for a function to be recursive, it must call itself at least once. When it calls itself, it places a pointer to itself on the stack for the recursive call's return. The stack, of course, is not the heap, and therefore a recursive function which uses only the heap is not possible.
(At least, not in C. Functional languages are optimized to re-use stack space and not allocate pointers for return calls)
在许多实现中，函数调用的参数存储在堆栈中。诸如要返回的地址之类的信息也可以存储在堆栈上。因此，在不使用堆栈的情况下使用递归函数可能是不可行的。
检查编译器文档，看看是否可以在不使用堆栈上任何空间的情况下调用函数。如果是这样，那么您已经上路了。
In many implementations, arguments to a function call are stored on the stack. Information such as the address to return to may also be stored on the stack. Thus having a recursive function without using the stack may not be feasible.
Check your compiler documentation to see if a function can be called without using any room on the stack. If so, you are on your way.
是的，可以仅使用堆来实现递归，并且在某些情况下这是非常可取的。例如，请参阅 Stackless Python。这样做的主要好处之一是整个线程可以变得可序列化，并且您实际上可以将线程从一台主机传送到另一台主机（甚至是不同的体系结构和操作系统！）。
Yes, it is possible to implement recursion using only the heap, and in some cases it's very desirable. For instance, see Stackless Python. One of the prime benefits of this is that an entire thread can become serializable and you can literally ship a thread from one host to another (even of a different architecture & operating system!).
我这样做：
然后...
通常，我将其实现为实用程序类“Recursor”
对象实现接口“IRecursable”
可以要求 Recursor 类递归深度优先或宽度优先。
我的实现还在根节点上调用 RecursionBegin() 和 RecursionEnd()，以便递归的类可以处理所需的任何初始化和清理代码。
递归类还可以让根通知每个被调用的对等点 - 允许它看到：
RecursionBegin() - 在递归开始之前调用一次。
RecursionElement() - 调用多次（可选）。
RecursionEnd() - 在递归结束后调用一次。
这些方法是 IRecursable 接口的一部分，可以重写以允许类灵活地使用递归器。
但是有一个更简洁的方法
有时我将这些实用程序移动到一个名为 Recursable 的类中，该类结合了类 Recursor 和接口 IRecursable 的功能……或者将它们完全组合到对象类中，这意味着该类将成为recursed 变得可自递归，不需要任何支持类。
希望这可以帮助人们开始将递归算法转换为基于堆的算法......并避免破坏堆栈或导致讨厌的堆栈溢出
TBH，递归是邪恶的，应该像瘟疫一样避免！ （除非您的语言允许真正的尾调用递归）
……尊重堆栈，它是宝贵的资源！
I do it this way :
then...
Usually, I implement this as a utility class "Recursor"
Objects implement the interface "IRecursable"
The Recursor class can be asked to recurse Depth-First or Width-First.
My implementation also calls RecursionBegin() and RecursionEnd() on the root node, so that the class being recursed can handle any initialisation and cleanup code required.
The recursed class can also have the root notified of each called peer - allowing it to see :
RecursionBegin() - Called once, before recursion starts.
RecursionElement() - Called multiple times (optional).
RecursionEnd() - Called once, after recursion ends.
These methods are a part of the IRecursable interface and can be overridden to allow the class to be flexible in how it uses the recurser.
But there is a more concise method
Sometimes I move these utilities into a single class called Recursable that combines the features of class Recursor and interface IRecursable… or combine them fully into the object class meaning that the class to be recursed becomes self-recursable, without any need for supporting classes.
Hope that helps someone make a start on converting Recursive algorithms to Heap-based algorithms... and avoid clobbering the stack or causing nasty Stack-Overflows
TBH, recursion is evil and should be avoided like the plague! (except where your language allows true tail-call recursion)
… respect the Stack, it is a precious resource!!!