recursion and linked lists

Discussion in 'Python' started by John Salerno, Apr 1, 2006.

  1. John Salerno

    John Salerno Guest

    Can someone explain to me how this works:

    def printBackward(list):
    if list == None: return
    head = list
    tail = list.next
    printBackward(tail)
    print head,

    3 2 1


    The printable value of node1 is 1, node2 is 2 and node 3 is 3.

    node1.next is node2, node2.next is node3 and node3.next is None.

    This might be painfully obvious, but I don't understand when the print
    statement is getting called. If you call printBackward with node1, then
    you skip the if statement, head becomes node1, tail becomes node2 and
    then you call printBackward again with node2. During this call you call
    printBackward again with node 3 and then the next time the if statement
    returns. So when does the print happen, and how does it print 3
    different values? It seems like you wouldn't get to it until the last
    time printBackward returns, and 'head' at that point would be 3, which
    is the first number printed. But doesn't it stop at this point? Where do
    2 and 1 come from?

    Thanks!
     
    John Salerno, Apr 1, 2006
    #1
    1. Advertisements

  2. John Salerno

    I V Guest

    Each time printBackward gets called, it has it's own separate 'head'
    variable. We could imagine they're all separate variables head1 for the
    first time printBackward is called, head2 for the second, and so on.
    The first time printBackwards gets called, it's local 'head' variable
    (head1) gets set to 1, and so on.
    Note that print gets called after _each_ time that printBackward
    returns. So, as the different calls to printBackward return, they print
    whatever 'head' was set to in that invocation. Now, logically enough,
    the last call to printBackward is the first to return, so the last
    value of 'head' is printed first, and so in in the reverse order of the
    list. Maybe this will help you visualize what is going on:

    call printBackward with arg [1, 2, 3]
    head1 = 1
    call printBackward with arg [2, 3]
    head2 = 2
    call printBackward with arg [3]
    head3 = 3
    call printBackward with arg None
    return
    print head3 ( == 3)
    return
    print head2 (== 2)
    return
    print head1 (== 1)
    return
     
    I V, Apr 1, 2006
    #2
    1. Advertisements

  3. John Salerno

    John Salerno Guest

    I V wrote:

    Oh, that helps! Now I'm starting to understand when exactly it returns
    each time.
     
    John Salerno, Apr 1, 2006
    #3
  4. John Salerno

    Ed Singleton Guest

    The way I got my head round this was to think of namespaces (I'm not
    sure how true this is though).

    I think of the first head variable as being:

    printBackward.head

    When it calls printBackward from within the first printBackward, thye
    second variable is:

    printBackward.printBackward.head

    and so on. It helps to keep it clear that they are entirely different.

    Ed
     
    Ed Singleton, Apr 7, 2006
    #4
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.