0

I'm writing a recursive function which swaps pairs in a singly linked list. In the function there's this line which works all fine: 

head.next.next, head.next = head, head.next.next

But if I switch the order to be like this: 

head.next, head.next.next = head.next.next, head

I get a RecursionError: maximum recursion depth exceeded error.

What is the difference between the two lines? How are they being executed by the interpreter?

Thanks!

Gal Shahar
  • 2,695
  • 1
  • 21
  • 29
  • can you elaborate? @ycao – Gal Shahar Jan 18 '20 at 13:15
  • 1
    https://stackoverflow.com/questions/8725673/multiple-assignment-and-evaluation-order-in-python – Roope Jan 18 '20 at 13:20
  • https://docs.python.org/3/reference/expressions.html#evaluation-order – k.wahome Jan 18 '20 at 13:26
  • 2
    Question was closed so can't do a proper answer anymore, but the answer is that first the "expression" (right-hand) is executed left to right, then the "target" (left hand) is executed left to right. So the second version creates a cycle: starting with `1 -> 2 -> 3` you'll first update that to `1 -> 3` (head.next = head.next.next) then `1 -> 3 -> 1` (head.next.next = head). – Masklinn Jan 18 '20 at 13:28
  • 1
    Reopening this because the marked duplicate does not actually address the cited behaviour. This example is different because the unpacking targets are dependent upon each other. – Karl Knechtel Jan 18 '20 at 14:08

2 Answers2

2

The difference is that in the second one, head.next is reassigned before head.next.next is evaluated, so the second assignment target (head.next).next uses the result from the first assignment to head.next.

The excellent Python Tutor tool can be used to visualise what happens when the code is run, which may help you to understand: I ran each piece of code using a list with the numbers 1, 2, 3; the image below shows the initial state of the list:

initial state

Here's the result after the first code; note that I created another reference to the Node(2), otherwise it would be lost:

code 1

Here's the result after reinitialising the linked list, and running the second code; again, I created another reference to the Node(2) to prevent it from being lost:

code 2

We can see that the second code creates a cycle, so that the list doesn't have an end any more. That means any recursive algorithm which tries to iterate through the list will not terminate, except by overflowing the call stack.

kaya3
  • 47,440
  • 4
  • 68
  • 97
1

Suppose head names element 0 of the list, which has a .next referring to element 1 etc. to start.

In the first case build the tuple (head, head.next.next), which is to say, (element 0, element 2). Then we assign those values to head.next.next and head.next respectively, and in that order. That is to say, the head.next (element 1 previously) has its next altered to refer to element 0, and the head (element 0) has its next altered to refer to element 2. We have reversed the element 0 -> element 1 link into an element 1 -> element 0 link, and by temporarily making element 0 connect to element 2, we can repeat the process.

In the second case, we simply have the operations swapped on both sides, so it would seem like the net effect should be the same. However, this time we are tripped up by a dependency. Because the assignment to head.next happens before the assignment to head.next.next, the head.next.next doesn't update the prior head.next, but the one we just set up. That is: element 0 is connected to element 2, but then element 2 (rather than element 1) is the head.next that gets connected to element 0. Now we have built a cycle between those two elements, and attempts to continue the procedure thus get stuck in a loop (if implemented iteratively, or in unbounded recursion as described by OP for a presumed recursive implementation).

Normal uses of this a, b = x, y syntax in Python involve a and b being unrelated. Here they are related, so the order of assignment matters, despite that the syntax is normally used specifically to avoid worrying about order of assignment (for "state updates"). Linked list logic is the sort of thing where order of assignment needs to be precise, which is another good reason not to implement this stuff yourself - except, of course, as an exercise to practice detailed and precise thinking about algorithms.

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153