c - C 中的递归堆栈

Question

在递归过程中创建了一个堆栈，该堆栈包含什么，它包含值还是存储操作数的地址

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;                 
}

在上面的代码中，剩余指针保持最后一个节点的地址，而第一个指针不断变化，即它从堆栈中获取值，而剩余指针则没有。所以首先我想了解递归堆栈，它的结构，它包含什么，它是如何工作的，并且感谢上面代码的解释

Answer 1

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