recursion and linked lists

[I V]

John Salerno wrote:
> 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

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.

> is the first number printed. But doesn't it stop at this point? Where do
> 2 and 1 come from?

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