passing pointer address in a recursive function in c

Question

Im trying to understand the below code:

void recursiveReverse(struct node **head_ref)
{
    struct node *first;
    struct node *rest;

    if (*head_ref == NULL)
       return;   

    first = *head_ref;  
    rest  = first->next;
    if (rest == NULL)
       return;   
    recursiveReverse(&rest);
    first->next->next  = first;  
    first->next  = NULL;          
    *head_ref = rest;     
}

I noticed that the variable rest is having the same value for all the recursion call once the code reached beyond the recursiveReverse(&rest). But first->next has different values. I was able to understand why first->next has different values by writing them on a stack and comparing it with each call. But i could not understand how rest is having the same value for all the calls instead of the (rest = first->next) from the stack. Please let me know if the question is not clear or if any details are needed. Thanks

Update: I observed that, arranging the parameters properly, if i call recursivereverse(rest) instead of revursivereverse(&rest), the rest value changes for every recursive call just like any other variable on the revursion stack. I could not understand what is the difference &rest is making in the call.

After the line recursiveReverse(&rest); is executed, the list is almost reversed. At that time, rest points to the last item of the list, which is same regardless of the level of nesting in the recursion. — R Sahu
– R Sahu, Commented Dec 6, 2014 at 6:51

Karthikeyan.R.S · Accepted Answer · 2014-12-06 07:06:43Z

2

Consider the following input.

1 2 3 4.

First Recursion,

*Head_ref = 1;//value of head_Ref
 first =1; // first=*head_ref;
 rest=2;// rest=first->next;

Second recursion,

*Head_ref = 2;//value of head_Ref
 first =2; // first=*head_ref;
 rest=3;// rest=first->next;

Third Recursion.

*Head_ref = 3;//value of head_Ref
 first =3; // first=*head_ref;
 rest=4;// rest=first->next;

Fourth Recursion,

*Head_ref = 4;//value of head_Ref
 first =4; // first=*head_ref;
 rest=NULL;// rest=first->next;

Condition fails, It come to the third recursion , where it called.

Third Recursion,

    first=3;
    first->next->next=first// here it means the rest link.
    first->next=NULL;// it will make the pointer that is end.
    *head_ref=rest; // making the starting address in this recursion

Now the list comes like this, 4 -> 3. Now the value of rest is changed into 4.

Now it come to the second recursion,

Rest will pointing 4, but the first->next is pointing to 3.

first=2;
rest=4;
first->next->next=first// here it means the rest link.
first->next=NULL;// it will make the pointer that is end.
*head_ref=rest; // making the starting address in this recursion

So now the head_ref is pointing to 4. Then now the list will be 4 -> 3 -> 2.

It comes to the first recursion,

Here,

first=1,rest=4, But first -> next =2.
first->next->next=first// here it means the rest link.
first->next=NULL;// it will make the pointer that is end.
*head_ref=rest; // making the starting address in this recursion

At finally it change into

4 -> 3 -> 2 -> 1.

So now the list is reversed. Here main thing make the *head_ref into last position at end of the recursion.

answered Dec 6, 2014 at 7:06

Karthikeyan.R.S

4,0512 gold badges21 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1455116 Over a year ago

Hi, but in the second recursion call, we have on the call stack, we have rest = first->next before the recursion. So rest should have whatever value that first->next is having right?..another thing i observed is, the program does not behave this way if i call reverse(rest) instead of reverse(&rest)

Karthikeyan.R.S Over a year ago

Before the recursion rest having the value that you are saying. In recursion we are passing the address of the rest. So the modification made in the another recursion that will be affect in this. Another thing , Even though rest is changed it's value, first pointer pointing position is not changed.

Akhil · Accepted Answer · 2014-12-06 12:28:34Z

consider a linked list 1->2->3->4. As per the recursiveReverse(), at the iteration of recursive function call when (rest == NULL) is satisfied(node '4'), *head_ref = 4;Now after this, the call returns to previous iteration(node '3'). Here basically rest(= '4') variable of the current iteration of function recursion(node '3') is actually *head_ref of last iteration(last node '4') where *head_ref was calculated as 4. hence at the end of the function in recursion(node '3'), we are doing *head_ref = rest;,ie. *head_ref = 4, since restis received as 4 from function iteration node = '4'. now at next consecutive recursive returns from these functions, address of *head_ref is returned, which remains same through and hence the statement *head_ref = rest; gives the same values through out.

Collectives™ on Stack Overflow

passing pointer address in a recursive function in c

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related