仅使用堆区域的递归

是否只使用堆区域进行递归示例?

在C中,基于函数调用的递归总是使用堆栈,几乎按定义。

如果您愿意将递归转换为迭代,那么可以仅使用堆空间,但这不是真正的递归。 您可以通过在堆中实现堆栈来实现。

某些问题可以使用尾递归 ,它会重复覆盖堆栈的相同区域。

你可以做一些疯狂的事情,比如malloc一个新区域,关闭中断以及其他所有事情(在许多系统上都不可能)并将堆栈指针设置为malloc区域。 从技术上讲,你仍在使用堆栈,但堆栈位置现在已经在堆上了。 这不是一个好主意,但它可以在一些具有这种控制级别的嵌入式系统上运行。

在许多实现中,函数调用的参数存储在堆栈中。 诸如要返回的地址之类的信息也可以存储在堆栈中。 因此,在不使用堆栈的情况下具有递归function可能是不可行的。

检查编译器文档以查看是否可以在不使用堆栈中的任何空间的情况下调用函数。 如果是这样,你就在路上。

为了使函数具有递归性,它必须至少调用一次。 当它调用自身时,它会在堆栈上放置一个指针,用于递归调用的返回。 当然,堆栈不是堆,因此不能使用仅使用堆的递归函数。

(至少,不在C语言中。function语言经过优化,可以重用堆栈空间而不为返回调用分配指针)

是的,可以仅使用堆来实现递归,在某些情况下,它是非常理想的。 例如,请参阅Stackless Python 。 这样做的一个主要好处是整个线程可以变成可序列化的,你可以将一个线程从一个主机传送到另一个主机(即使是不同的架构和操作系统!)。