[Tutor] treeTraversal, nested return?

[jjcrump at uw.edu]

Thanks to Matthew and Denis for trying to enlighten me. Thanks to your 
clues I've made some progress; however, I can't seem to get the hang of 
the usual recursion trick of keeping track of the level one is on. It 
doesn't work, I suppose, because the data structure I'm traversing isn't 
actually nested, its a flat series of lists of tuples.

I did finally get a function to traverse the "tree-like" data coming from 
the db

getRecord() returns a tuple of record-type, record-id, parent-id, and 
title, thus:
('work', 47302, 47301, 'record title')

getImages(id) returns a list of 'image' tuples whose parent-id is id
getWorks(id) returns a list of 'work' tuples whose parent-id is id

works can be nodes, images can't

so:

    def makeDecendentList(id, result):
       result.append(getRecord(id))
       if getImages(id):
          for x in getImages(id):
             result.append(x)
       if not getWorks(id):
          return
       else:
          for y in getWorks(id):
             makeDecendentList(y[1],result)
       return result

called with the empty list as the second argument.

Well and good. This walks the 'tree' (following the parent-ids) and 
returns me a list of all the decendents of id. But what I wanted was a 
nested data structure.

In the fashion of an ape given a typewriter and sufficient time, I trial 
and errored my way to this:

    def makeNestedLists(id):
       result = []
       result.append(getRecord(id))
       result.extend(getImages(id))
       if not getWorks(id):
          return result
       else:
          result.extend([makeNestedLists(x[1]) for x in getWorks(id)])
       return result

To my surprise, this gets me exactly what I wanted, eg:

    [  ('work', 47301, 47254, 'a title'),
       ('image', 36871, 47301, 'a title'),
       ('image', 36872, 47301, 'a title'),
       [  ('work', 47302, 47301, 'a title'),
          ('image', 10706, 47302, 'a title'),
          ('image', 10725, 47302, 'a title')
       ]
    ]

To my surprise, I say, because it looks like it shouldn't work at all with 
the result being set to the empty list with each recursion; moreover, if I 
spell out the loop in the list comp like this:

    def makeNestedLists(id):
       result = []
       result.append(getRecord(id))
       result.extend(getImages(id))
       if not getWorks(id):
          return result
       else:
          for x in getWorks(id):
             result.extend(makeNestedLists(x[1]))
       return result

I once again get a flat list of all the decendents of id.

I know it's sad, but can any wise tutor explain to me what's going on in 
the code that I myself wrote?

Thanks,
Jon