469,342 Members | 5,614 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,342 developers. It's quick & easy.

recursion and linked lists

Can someone explain to me how this works:

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

printBackward(node1)

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!
Apr 1 '06 #1
3 1636
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

Apr 1 '06 #2
I V wrote:

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.


Oh, that helps! Now I'm starting to understand when exactly it returns
each time.
Apr 1 '06 #3
On 01/04/06, John Salerno <jo******@nospamgmail.com> wrote:
I V wrote:

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.


Oh, that helps! Now I'm starting to understand when exactly it returns
each time.


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
Apr 7 '06 #4

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by Chris Ritchey | last post: by
11 posts views Thread by hana1 | last post: by
1 post views Thread by Anthony Moss | last post: by
3 posts views Thread by s_subbarayan | last post: by
6 posts views Thread by paudirac | last post: by
17 posts views Thread by Foodbank | last post: by
3 posts views Thread by Little | last post: by
51 posts views Thread by Joerg Schoen | last post: by
23 posts views Thread by Just Another Victim of the Ambient Morality | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
1 post views Thread by Marylou17 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.