recursion confusion

[Erik Max Francis]

Jon Schull wrote:

> Sometimes recursion befuddles me.  This is one of those times.
> 
> I want to convert a graph structure into a nested string
> For example I want this...
> 
> g={0:[], 1:[11], 2:[21,  22], 22:[221,222]}
> 
> ...to become this
>         "0,     1[11], 2 [21,  22[221, 222]] "
> 
> (with 221 and 222 nested under 22 which is also nested under 2)
> 
> Of course, I want this to work for arbitrary nesting, and for strings
> as well as numbers.

Seems relatively straightforward.  First, get a list of the graph nodes
that are top-level (i.e., those which are not the children of any node).
Then, write a recursive function which displays a node by its ID, and
its children, if it has any, in brackets afterward.  Then take that list
of top-level nodes and run the function on each one, separating the
result with commas.  Add spaces and/or formatting to taste.

The function would be something like this:

	def render(node):
	    result = str(node)
	    children = getNodeChildren(node) # write this function
	    if children:
	        result += '[%s]' % ', '.join(map(render, children))
	    return result

>From looking at your routine, it looks like getNodeChildren would simply
be written as

	def getNodeChildren(node):
	    return G.get(node, []) # calling your global dictionary G

Obviously, this might need improvement depending on your graph.  If it
has cycle, then this will recurse indefinitely.

I leave it as an exercise for you to figure out how to find the
top-level nodes.  (Hint:  What property makes them top-level?  How would
you test for that?  If you use a recursive algorith, how would you
communicate that information down through the function calls?)

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ The people are to be taken in very small doses.
\__/ Ralph Waldo Emerson
    Erik Max Francis' bookmarks / http://www.alcyone.com/max/links/
 A highly categorized list of Web links.