[Tutor] lists and recursion

[Kent Johnson]

Christopher Spears wrote:
> I am working out of How To Think Like A Computer
> Scientist.  Here is the code for a module called
> node.py:
>
> def printList(node):
> 		nodeList = []
> 		while node:
> 			nodeList.append(node.cargo)
> 			node = node.next
> 		print nodeList
> 		
> def printBackward(node):
> 	if node == None: return
> 	head = node
> 	tail = node.next
> 	printBackward(tail)
> 	print head,
> 		
> class Node:
> 	def __init__(self, cargo=None, next=None):
> 		self.cargo = cargo
> 		self.next = next
> 		
> 	def __str__(self):
> 		return str(self.cargo)
> 		
>
> I'm trying to figure out how the printBackward
> function works.  I understand it moves up a linked
> list until it reaches the end of the list.  Why does
> it print every node?  Shouldn't it just print the last
> one?
printBackward() scans to the end of the list by making nested calls to 
itself. Each call is matched by a return which returns to the place 
where it was in the next call up the stack. So the most deeply nested 
call will print head and return to the next-most-deeply-nested call 
which will print head, etc.

Each call has its own set of local variables (called a stack frame) - 
its own value for node, head and tail. So the print statements print all 
the cargo in the list.

We just had a discussion of recursion, you might want to look at it - 
though the code is a bit more complex than this example.
http://mail.python.org/pipermail/tutor/2006-July/048081.html

Kent