CODEWITHSUNDEEP
pythonrecursionlinked-list
Amon
Amon

Reputation: 2971

Understanding control flow in traversing through list

Here I have a class that contructs a node and a function that prints out the node in reverse order:

class LLNode(object):
    def __init__(self, data):
        '''(LLNode, object) -> NoneType
        Create a new node to hold data
        '''
        self.data = data
        self.link = None
    def __str__(self):
        return str(self.data)


def reverse_list(L):
    if L is None: return
    head = L
    tail = head.link
    reverse_list(tail)
    print(head, end=' ')



list1 = LLNode(1)
list1.link = LLNode(2)


print(reverse_list(list1))

What I don't understand is when the print statement runs, since reverse_list(tail) is placed before it, to me it looks like it is ignored. What I find is if I switch those two lines the program will print the linked-list in-order, which makes sense to me. How does putting print after make it print in reverse? I'm not understanding the flow here.

Upvotes: 0

Views: 59

Answers (2)

jonrsharpe
jonrsharpe

Reputation: 122096

Because by printing after the recursive call, it happens when control returns to the calling function, on the way back up the calls. Here is a simple example:

>>> def recur(x):
    print("Going down ({0}).".format(x))
    if not x:
        print("Hit bottom")
        print("Coming up ({0}).".format(x))
        return None
    recur(x-1)
    print("Coming up ({0}).".format(x))


>>> recur(2)
Going down (2).
Going down (1).
Going down (0).
Hit bottom
Coming up (0).
Coming up (1).
Coming up (2).

Upvotes: 1

BrenBarn
BrenBarn

Reputation: 251468

Notice that what it prints is the head of the list. At each step, it "peels off" the first element of the list, stores it, then recursively calls itself on the rest of the list. On the last call, it will have only one element left. It will then print that element and return to the previous call, which will print the element it peeled off, which was the second-to-last element. That will then return to the previous call, which will print the element before that, and so on.

You can think of it as having a deck of cards, and the algorithm is, "Build a new stack by taking the top card off the deck and putting it down on top of the new stack. After you've done this with all the cards, go through the new stack from top to bottom and look at each card." As you go through the deck from top to bottom, you will put cards in the new stack from bottom to top, so you reverse the stack. Only after you've stacked all the cards into this reverse stack do you go back and look at them (which is like "printing" them), at which point you're looking at them in reverse order.

Upvotes: 1

Related Questions