在递归过程中创建了一个堆栈,该堆栈包含什么,它包含值还是存储操作数的地址
void recursiveReverse(struct node** head_ref)
{
struct node* first;
struct node* rest;
/* empty list */
if (*head_ref == NULL)
return;
/* suppose first = {1, 2, 3}, rest = {2, 3} */
first = *head_ref;
rest = first->next;
/* List has only one node */
if (rest == NULL)
return;
/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next = first;
/* tricky step -- see the diagram */
first->next = NULL;
/* fix the head pointer */
*head_ref = rest;
}
在上面的代码中,剩余指针保持最后一个节点的地址,而第一个指针不断变化,即它从堆栈中获取值,而剩余指针则没有。 所以首先我想了解递归堆栈,它的结构,它包含什么,它是如何工作的,并且感谢上面代码的解释
最佳答案
i want to know about recursive stack, it's structure, what it contains, how it works
递归函数 与任何其他函数完全相似。因此,对于 递归函数 的瞬时调用,它将像普通函数一样维护堆栈。每次函数声明一个新变量时,它都会被压入到堆栈中。然后每次函数退出时,该函数压入堆栈的所有变量都将被释放(也就是说,它们被删除)。一旦堆栈变量被释放,该内存区域就可用于其他堆栈变量。
所以当一个递归函数被调用时,它的所有变量都被压入到栈中,当它返回时,栈变量被释放。请注意,自动局部变量被分配为单个 block ,堆栈指针提前到足以说明它们大小的总和。
长话短说,递归函数的每次调用都会占用堆栈中的一 block 内存。请看以下 C 中的无限递归示例。
int foo()
{
int someVariable;
return foo();
}
函数 foo 在被调用时会继续调用自身,每次都会在堆栈上分配一 block 额外的空间,直到堆栈溢出导致段错误。
有关其他信息,如果我们将 foo()
声明如下:
int foo()
{
double x[1024];
return foo();
}
然后每次递归调用,都会在栈中为x
分配一个额外的1024 * sizeof(double)
内存。但是使用 malloc()
将分配 heap 内存而不是 stack。
最后,每次调用递归函数,包括返回值,返回地址也被压入栈中。
如您所见,每次递归调用都会推送一个新的堆栈帧,然后如果递归未能达到基本情况,堆栈将很快耗尽并导致堆栈溢出。
引用:Stack based memory allocation , Stack overflow和 Memory Stack vs Heap
关于c - C 中的递归堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31065864/