CODEWITHSUNDEEP
crecursionlinked-listreverse
Scared
Scared

Reputation: 301

Help in understanding code snippet that reverses linked list using recursion

I am studying for an exam with Linked Lists in C. I found myself a "reviewer" it had this snippet of code. For the life of me, I cannot understand how the rest is reversed. Here it is... it is from Linked List Problems by Mr.Nick Parlante (taken CIS Library, Stanford). I will put in Mr. Nick's Comments.

RecursiveReverse() Solution

Probably the hardest part is accepting the concept that the RecursiveReverse(&rest) does in fact reverse the rest. Then then there's a trick to getting the one front node all the way to the end of the list. Make a drawing to see how the trick works.

void RecursiveReverse(struct node** headRef) {
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case
first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
if (rest == NULL) return; // empty rest base case
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                         // after: rest = {3, 2}
first->next->next = first; // put the first elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer

}

I've made countless drawings in attempts to trace what is going on, and I just cannot understand how RecursiveRest(&rest) actually reverses the rest. Please help. I am getting quite frustrated. What I end up getting is smaller "rest"s..and nothing is reversed. Thank you so much in advance.

Upvotes: 2

Views: 813

Answers (2)

Mihai Toader
Mihai Toader

Reputation: 12243

Recursion is usually hard to comprehend because it's hard to see how it decomposes into basic steps.

It is usually easier to think of the recursive part as already finished and only reason about the combination step (this is most useful when designing the algorithm).

When you are trying to visualize how an recursive algorithm works you have to keep in mind that there are two processes at work:

  • the decomposition of the original problem in smaller problems until you find the termination case
  • the solving of the termination case
  • the combination of the results.

It's like a two way street. First you go one way until the end case while breaking up the problem. You then solve the end case. After that you return at the beginning while combining the partial results.

For your case it might go like this. Note that [A-B] means a list.

[A-B-C-D-E] // RecursiveReverse([A, B, C, D, E])
(A [B-C-D-E]) // this means we are calling RecursiveReverse([B, C, D, E])
(A (B [C-D-E])) // this means we are calling RecursiveReverse([C, D, E])
(A (B (C [D-E]))) // this means we are calling RecursiveReverse([D, E])
(A (B (C (D [E])))) // this means we are calling RecursiveReverse([E]) 
                    // hit the end case and solve it trivially
(A (B (C (D [E])))) // solved
(A (B (C [E-D]))) // and go back while applying the combination case
(A (B [E-D-C])) // combine
(A [E-D-C-B]) // combine
[E-D-C-B-A] // combine

Hope this helps.

Upvotes: 7

George
George

Reputation: 3845

  1. At each step the code remembers the current and the next node (first and rest).
  2. Assume that RecursiveReverse(&rest) works and reverses the remaining list.
  3. Then the rest node will be at the last position when the call returns. So you just have to check the last three lines of code.
  4. You will see that rest is changed to point at first (first->next->next = first), and first points to NULL (first->next = NULL), i.e. you move first to the end of the list.

Upvotes: 1

Related Questions