A little recursion help please (lists)

[tucanoj]

I've been playing around with recursion a little bit, admittedly it's been some time since I've used it, and I'm feeling pretty rusty. I was simply trying to recursively reverse a linked list and wasn't getting anywhere and finally google'd some code and came across the below snippet,

node * reverse(node *head) {
   node *temp;
   if (!head->next) temp = head;
   else {
      temp = reverse(head->next);
      head->next->next = head;
      head->next = NULL;
   }
   return temp;
}

The terminating condition is pretty obvious, but after the recursive call is where the confusion comes in. I'll walk through this, and if anybody would be so kind, could you please explain the section where confusion lies?

So, as each stack frame is pushed we're advancing down the list until our next pointer is null (i.e. we're at the last node). Let's say my list is the following,

[1]->[2]->[3]->[4]->[5]->NULL;

So when we start the stack unwinding when our if() conditional is true the following should hold.
- head points to node [5]
- temp is assigned head
- we return temp on line 9

Now we make our way to line 6 and here is where the confusion starts. The current stack frame has head pointing to node [5], head's next = NULL, so what does line 6 do? Specifically,

head->next->next = head;

After this is executed we know head->next->next is pointing back to itself. This confuses the hell out of me. Then moving on, why is line 7 setting head's next to NULL?

These last two steps seem to set up the chaining, but I'm lost as to what's going on.

[griswolf]

Mmm. I think you are working too hard at this. I used to do the same thing until one day, after reading again about recursion I went to bed in an iterative world and woke the next day in a recursive one. Once this happens, you don't need to think about what is happening on the stack, you just need to make sure that

1. The code works correctly at the end condition
2. The code works correctly anywhere in the middle
3. For production quality code only: Code works on degenerate cases too.

For me, a math major, this came with the realization that recursion and mathematical induction are mentally the same process.

Looking at the code, we can see that it doesn't work for an empty list, so this is not production quality code, but for a one-element list, line 3 applies and we get the same list back: Correct.

For longer lists assume that line 5 works correctly so we get head == [1] and temp = reverse([2] ...->[n]->NULL) which is in fact [N]->...[2]->NULL . So far good. Now we know that head->next == [2] (because head hasn't changed yet, so its next hasn't either), so line 6 puts head after [2] and line 7 finalizes the list and line 9 returns the head of the list that was reversed at line 5: [n]->...[2]->[1]->NULL which is correct.

Finally, realize that we have seen it work for lists of any length, since we didn't specify n, so it works for all lists with at least one element.

[tucanoj]

Yes, I agree, definitely not very robust code, but I wasn't concerned with boundary conditions, just trying to brush off the old recursion.

Recursion sure is good 'ol induction at its heart, but I jumped into the machine and started thinking about stack frames and I think that's definitely what started the confusion. I was looking at tail recursion and optimization before I thought about this, so maybe that's where it came from. Perhaps I'll look at the assembly and get a better feel at the machine level.

I always feel like I have to trick myself into thinking recursively, and your reply definitely reminded me of the mindset I need to take when looking at these types of problems. Thanks for the explanation, it really helped.

[wisaacs]

It's plain wrong

[wisaacs]

wups, sorry. My bad.

[tucanoj]

So, I wanted to get an idea what was happening "underneath the hood", and I opened up the debugger and started stepping through the stack, something I should have done in the first place. Below is the stack unwinding step-by-step (or frame-by-frame). Maybe this will help someone just getting into recursion or confused with a similar problem.

Assumptions:
- we have recursed until our terminating condition has become true and execution is halted there waiting for the stack to unwind (line 4 below).
- before unwinding the most recent frame pushed onto the stack is frame 0, followed by frame 1, ..., frame n.
- when I speak about a specific line (e.g. line 4) I'm always referring to the code within the function reverse(...)
- list is as follows before reversal:

[1]->[2]->[3]->[4]->[5]->NULL

node * reverse(node *head) {
   node *temp;
   if (!head->next) {
      temp = head;
   }
   else {
      temp = reverse(head->next);
      head->next->next = head;
      head->next = NULL;
   }
   return temp;
}

picking up from our assumption we sit at line 4. 'temp' is assigned 'head' and the stack frame is,

(frame 0)
head = [5]
head->next = NULL

temp  = [5]
temp->next = NULL

execution jumps to line 11 and 'temp' is returned and we pop to stack frame 1 and execution moves to line 8. Frame 1 is is as follows before executing line 8,

(frame 1)
head = [4]
head->next = [5]

temp = [5]
temp->next = NULL

After executing line 8,

(frame 1)
head = [4]
head->next = [5]
head->next->next = [4]

temp = [5]
temp->next = [4]

It's this step that initially threw me off, but the recursion mixed with indirect pointer manipulation can be a bit subtle. Here is a brief explanation. Since initially 'temp' was assigned to what 'head' was pointing at, before the stack unwinding commenced (i.e. line 4), they were both pointing at the same address in frame 0 (i.e. [5]). Now, when we make it to frame 1 'head' in that stack frame points to [4] and 'head->next' points to [5] (as shown above). When we execute line 8 (i.e. head->next->next = head) we are saying essentially [5] points to [4]. How you say? The key is to remember 'temp' points to [5] (what was head in frame 0), so we have indirectly set temp's next pointer to point to head (in frame 1), which is [4] (caused by line 8). Confused yet? Now we execute line 9, and head->next = NULL. Now time to switch back and think how this effects 'temp'. Remember that 'temp->next' points to 'head' (head in frame 1 that is), so by setting 'head->next = NULL' we are setting the end of temp's list to null (i.e. null terminating the 'temp' list). More of that confusing indirect pointer manipulation.

If you're a new comer to recursion (and pointers as well) and are not confused after all of this you're owed a big congrats. If you can follow the above you can unwind the stack for the subsequent frames and see how 'temp' is built up. Consider it an exercise for the reader (yes, I went there).

Things to remember,
- 'temp' is indirectly manipulated by lines 8, 9.
- It's best to think of 'temp' and 'head' as two separate lists pointing to the same memory.
- head is pretty much "ruined" in each stack frame and only serves to manipulate temp. All if this is OK since as we unwind the stack (i.e. pop off a new stack frame) we get a fresh copy of the state 'head' was in previously.

Feel free to correct/criticize anything I've written, it's late and I'm tired and can't guarantee I haven't made any slight mistakes, but the general idea should hold.