Python Recursion through objects and child objects, Printing child depth numbers

Question

I have a simple class with an attribute that can contain a list of objects of one class

class BoxItem: def __init__(self, name, **kw): self.name = name self.boxItems = [] ... #more attributes here box1 = BoxItem('Normal Box') box2 = BoxItem('Friendly Box') box3 = BoxItem('Cool Box') box4 = BoxItem('Big Box', [box1, box2]) #contains some children example = BoxItem('Example Box', [box4,box3]) #contains another level of children 

Working with the example object, I would like to maneuver the depth of all possible child cells that it can have and print objects formatted like this:

 1 Example Box 1.1 Big Box 1.1.1 Normal Box 1.1.2 Friendly Box 1.2 Cool Box 

The relationship between them is not required, just need to clearly show the format of the tree. I can go down the objects and print their names, but I can’t print the front numbers showing the parent / child relationship. (1, 1,1, 1,2 ...)

Thanks in advance for your help :)

Edit Here's what I've worked with so far

 def print_boxes(box_list): node_count = 0 for box in box_list: node_count += 1 print str(node_count)+' '+box.name #prints out the root box recursive_search(box,node_count) def recursive_search(box,node_count): #recursive automatically level = 0 for child in box.boxItems: level += 1 for x in range(len(child.boxItems)): print x+1 #this prints out some proper numbers print "level: "+str(level) #experiment with level print child.name #prints out child box name recursive_search(child,node_count) #runs the function again inside the function 

Answer 1

I think this might be more useful for you if I post a working example of how to do this, rather than going through where you have code problems. We could have a thorough understanding of this. Your code has the right idea that it should track the depth as it arrives. But the only thing that is missing is the feeling of nested depth (tree). He knows only the previous node_count , and then its current counter.

My example uses closure to run a depth tracking object, and then creates an internal function for the recursive part.

 def recurse(box): boxes = not isinstance(box, (list, tuple)) and [box] or box depth = [1] def wrapped(box): depthStr = '.'.join([str(i) for i in depth]) print "%s %s" % (depthStr, box.name) depth.append(1) for child in box.boxItems: wrapped(child) depth[-1] += 1 depth.pop() for box in boxes: wrapped(box) depth[0] += 1 

Example output from your examples:

 >>> recurse(example) 1 Example Box 1.1 Big Box 1.1.1 Normal Box 1.1.2 Friendly Box 1.2 Cool Box >>> recurse([example, example]) 1 Example Box 1.1 Big Box 1.1.1 Normal Box 1.1.2 Friendly Box 1.2 Cool Box 2 Example Box 2.1 Big Box 2.1.1 Normal Box 2.1.2 Friendly Box 2.2 Cool Box 

Violation of this:

First, we take the box argument and automatically convert it locally to a list if you only passed it in one field. Thus, you can pass either a single box object or a list / tuple of them.

depth is our depth tracker. Its a list of ints, which we will grow and contract as we recurs. It starts with 1 for the first item / first level. Over time, it may look like this: [1,1,2,3,1] depending on how deep it goes. This is the main difference between my code and yours . Each recursion has access to this state.

Now we have this internal wrapped function. He is going to take the current item and print it, and then iterate over his children. We get our print string by entering the current depth list and then the name.

Each time we drop into a child list, we add an initial level of 1 to our depth list, and when we exit this child cycle, we return it again. For each child in this loop, we increment this last element up.

Outside of this internal wrapped function, we start all this by sorting through our initial fields, calling wrapped , and then increasing our first level.

The inner wrapped function uses a list of depths in closure. I bet that others can offer some additional improvements in this, but this is what I came up with as an example.

A note about function arguments

We could also design a recurse instead of a list of variables of variable length instead of checking a list. It will look like this (and get rid of this first check boxes = ):

 def recurse(*boxes): #boxes will always come in as a tuple no matter what >>> recurse(example) >>> recurse(example, example, example) 

And if you initially started with a list of elements, you can pass it by doing:

 >>> boxes = [example, example, example] >>> recurse(*example) # this will unpack your list into args 

Answer 2

You have two options:

• Keep an eye out for more information as an extra parameter in your recursion, for example. myRecursiveFunction(..., ancestry=[])
• Each BoxItem block keeps track of its parent, whenever it is embedded in BoxItem (in the __init__ constructor, set child.parent = self for each child). This is bad if you plan to use BoxItem in multiple blocks.