C中的递归堆栈 [英] Recursive Stack in C

问题描述

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

during recursion a stack is created what does that stack contains, does it contains the values or it stores the addresses of the operands

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

在上面的代码中，rest指针维护最后一个节点的地址，而第一个指针不断变化，即它从堆栈中获取值而rest指针不是.所以首先我想了解递归堆栈，它的结构，它所包含的内容，它的工作方式以及对以上代码的解释

in above code the rest pointer maintains the address of the last node while the first pointer keeps on changing ,i.e it is taking values from the stack while rest pointer not . so first i want to know about recursive stack , it's structure, what it contains, how it works and the explanation of the above code is appreciated

推荐答案

我想了解递归堆栈，它的结构，它包含的内容，如何工作

i want to know about recursive stack, it's structure, what it contains, how it works

递归函数与任何其他函数完全相似.因此，对于递归函数的瞬时调用，它将像普通函数一样维护堆栈.每当函数声明一个新变量时，都会将其推入到堆栈中.然后，每次函数退出时，该函数压入堆栈的所有变量都将被释放(也就是说，它们将被删除).释放堆栈变量后，该内存区域将可用于其他堆栈变量.

A recursive function is exactly similar with any other function. So for a instantaneous call of recursive function, it will maintain stack as normal function does. Every time a function declares a new variable, it is pushed onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

因此，当调用递归函数时，将其所有变量推入到堆栈上，然后当其返回时，将释放堆栈变量.请注意，自动局部变量被分配为单个块，并且堆栈指针提前到足以说明它们的大小之和.

So when a recursive function is called, all its variable is pushed onto the stack, and when it returns, stack variable is freed then. Note that, automatic local variables are allocated as a single block and stack pointer advanced far enough to account for the sum of their sizes.

长话短说，每次递归函数的调用都会占用堆栈中的一块内存.请看下面的C中无限递归示例.

Long story short, each call of a recursive function will occupy a block of memory in stack. Look at the following example of infinite recursion in C.

int foo() 
{
     int someVariable;
     return foo();
}

函数foo在被调用时会继续调用自身，每次都在堆栈上分配一块额外的空间，直到堆栈溢出导致分段错误为止.

The function foo, when it is invoked, continues to invoke itself, allocating a block of additional space on the stack each time, until the stack overflows resulting in a segmentation fault.

有关其他信息，如果我们声明 foo()如下所示:

For additional information, if we declare foo() as like the following:

int foo() 
{
    double x[1024];
    return foo();
} 

然后，每个递归调用将在堆栈中为 x 分配 1024 * sizeof(double)的额外内存.但是使用 malloc()将分配 heap 内存，而不是 stack .

Then each recursive call, an additional memory of 1024 * sizeof(double) will be allocated in the stack for x. But using malloc() will allocate heap memory instead of stack.

最后，每次调用递归函数(包括返回值)时，返回地址也会被压入堆栈.

Finally, each time the recursive function is called, including the return value, the return address also pushed onto the stack.

如您所见，每个递归调用都会推送一个新的堆栈帧，然后，如果递归未能达到基本情况，则堆栈将很快耗尽，并导致堆栈溢出.

As you see, each recursive call pushes a new stack frame then if the recursion fails to reach a base case, the stack will quickly exhausted and cause Stack Overflow.

参考:基于堆栈的内存分配，内存堆栈vs堆

这篇关于C中的递归堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！