Recursive Stack in C

Question

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

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

One important thing to know, whenever the `recursiveReverse()` method is called (recursively or from any other caller), the return address is pushed onto stack. — mazhar islam, Jun 26 '15 at 05:55
This is C, so values of parameters are on the stack along with return address, return value, etc. Have a look at "stack frame" on the web. — Jean-Baptiste Yunès, Jun 26 '15 at 06:21

mazhar islam · Answer 1 · 2015-06-26T06:38:26.257

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.

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

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.

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

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

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.

Reference: Stack based memory allocation, Stack overflow and Memory Stack vs Heap

Recursive Stack in C

1 Answers1

Linked