Recursively traversing a tree in a collection in Python [duplicate]

I have 100 collections and they form a complex tree structure.
I would like to enable the Holdout and Indirect Only options for the 50 specified collections from the entire collection.

In order to properly handle the tree of collections, I can predict the maximum depth and write for loops in layers, but I found a hint that the recursive function is excellent at solving this type of problem.

However, recursion was difficult for me, so I failed to write my own code.

How can I write a recursion that digs through a collection of tree structures to the end and then returns back?

• Hi. This sounds a bit like it could be an XY problem. Recursing through the tree could be the answer, but without more details about what you actually want to do (what are the requirements for which collections are changed?) we don't know. It may be that the solution that solves your actual problem doesn't require recursion at all. I suggesting focusing your question (and it's title) on the problem and not the potential answer. Jul 19 '20 at 20:20
• @RayMairlot If your collection has 4 children, you can solve the problem with quadruple for loops. However, as my project progresses, new collections are added and new child collections are added. In other words, the maximum depth of the tree cannot be accurately predicted. That's why I want to use recursion instead of for loops. Are there other techniques to solve this? Jul 19 '20 at 23:33
• I understand that. And as I said, if you describe your problem in more detail, i.e. how you're determining which collections to change, recursion might not be needed. So yes, there might be other ways to solve this if you focus your question on the problem and not recursion. Jul 20 '20 at 0:16
• Call stacks are extremely expensive in most of the programming language. Although Pythonic method will use a lot of call stack for sure, but they might not be suitable to use in massive data like multiple dimension array, or a tree like object which might be very big. But in your case, 100 is a pretty okay amount for a recursive function. Jul 21 '20 at 3:28
• See blender.stackexchange.com/a/167889/15543 See also blender.stackexchange.com/questions/157562/… as @RayMairlot pointed out recursion may not be needed, it is quite likely simpler to iterate bpy.data.collections and set for the 50 of 100. Jul 21 '20 at 9:59

If the maximum depth of the tree cannot be accurately predicted, then you cannot use recursive way or you might encounter stack overflow unless you are able and willing to deal with system call stack.

You can, however, use a custom stack (list in python) record the data you need to process. And pop them out to examine, while append new task you found in that loop.

condition = lambda collect: "foobar" in collect.name
dosomething = lambda collect: None

dealing_stack = []

# Blender store all collection in list not a tree (or a tree-liked list?)
for collect in bpy.data.collections:
if condition(collect) and collect not in dealing_stack:
dealing_stack.append(collect)

# record processed object, not sure if id won't change in dealthis
processed_list = []

while dealing_stack:
dealthis = dealing_stack.pop()
try:
dosomething(dealthis)
except:
raise
finally:
processed_list.append(dealthis)
dealing_stack.extend(
[
obj
for obj in dealthis.children
if obj not in processed_list
]
)


While the recursive method indeed been more flexible in dealing with tree like structure:

condition = lambda collect: "foobar" in collect.name
dosomething = lambda collect: None

def deal_these_collection(collections, condition, callback=[]):
if not collections:
return

for subcollect in collections:
is_specified = condition(subcollect)
if isinstance(subcollect, list):
deal_these_collection(
collections = subcollect,
condition = lambda:True if is_specified else condition,
callback
)
elif is_specified:
for call in callback:
if callable(call):
call(subcollect)
else:
# not target
pass

deal_these_collection(bpy.data.collections, condition, [dosomething])



Please be aware of stack overflow problem when using recursion in large and deep tree, you must know your algorithm very well and prepare some stack memorization technique to prevent the problem and make your program more efficient.

Personal opinion

If a program can be written in iterative method, then use iterative unless using recursive will "Strongly" enhance the readability of code. When code is in Python, the readability should be consider first. Most of the recursive method will let other confuse what's going on in code, and also making it hard to debug.

So unless the problem you deal is commonly dealt in recursive way, and you can list up bunch of merit to use it. Just use iterative way. Writing iterative method in Python should be easy due to the python duck-type list and a lot of handy expression.

• Hello, this should be dealthis = dealing_stack.pop() instead of dealthis = dealing_stack(pop). Also, if a collection and its children are in the initial dealing_stack (ie. their name contains "foobar"), your code will dosomething twice on it since you don't check if the children are already in the dealing_stack Jul 21 '20 at 7:39
• @Gorgious Thanks for the correction. Yes I assume that dosomething check some properties, and there could be a marking list to check whether object is been processed. Jul 21 '20 at 8:44
• Yup just wanted to point it out :) Anyway if dosomething only deactivates visibility for example this is not a problem if it's done twice. However if the method toggles visibility, it will look like it does nothing. I agree that using recursion for this particular problem is overkill since we have access to every collection very easily as a list Jul 21 '20 at 8:49