I have a database that models a foldering relationship to n
levels of nesting. For any given folder, I want to generate a list of all child folders.
Assuming I have a function called getChildFolders[]
, what is the most efficient way to call this kind of recursive loop?
The following code works for 4 levels of nesting, but I'd like more flexibility in either specifying the depth of recursion, or in intelligently stopping the loop when there are no more children to follow.
folder_ids = []
folder_ids.append[folder.id]
for entry in child_folders:
folder_ids.append[entry.id]
child_folders_1 = getChildFolders[entry.id]
for entry_1 in child_folders_1:
folder_ids.append[entry_1.id]
child_folders_2 = getChildFolders[entry_1.id]
for entry_2 in child_folders_2:
folder_ids.append[entry_2.id]
child_folders_3 = getChildFolders[entry_2.id]
for entry_3 in child_folders_3:
folder_ids.append[entry_3.id]
asked Nov 9, 2010 at 21:31
1
A recursive function is a nice way to do this:
def collect_folders[start, depth=-1]
""" negative depths means unlimited recursion """
folder_ids = []
# recursive function that collects all the ids in `acc`
def recurse[current, depth]:
folder_ids.append[current.id]
if depth != 0:
for folder in getChildFolders[current.id]:
# recursive call for each subfolder
recurse[folder, depth-1]
recurse[start, depth] # starts the recursion
return folder_ids
answered Nov 9, 2010 at 21:39
Jochen RitzelJochen Ritzel
101k29 gold badges195 silver badges190 bronze badges
6
I generally avoid recursion like the plague in python because it's slow and because of the whole stack overflow error thing.
def collect_folders[start]:
stack = [start.id]
folder_ids = []
while stack:
cur_id = stack.pop[]
folder_ids.append[cur_id]
stack.extend[folder.id for folder in getChildFolders[cur_id]]
return folder_ids
This assumes that getChildFolders
returns an empty list when there are no children. If
it does something else, like return a sentinel value or raise an exception, then modifications will have to be made.
answered Nov 9, 2010 at 21:43
aaronasterlingaaronasterling
66.6k20 gold badges123 silver badges125 bronze badges
1
def my_recursive_function[x, y, depth=0, MAX_DEPTH=20]:
if depth > MAX_DEPTH:
return exhausted[]
elif something[x]:
my_recursive_function[frob[x], frob[y], depth + 1]
elif query[y]:
my_recursive_function[mangle[x], munge[y], depth + 1]
else:
process[x, y]
# A normal call looks like this.
my_recursive_function[a, b]
# If you're in a hurry,
my_recursive_function[a, b, MAX_DEPTH=5]
# Or have a lot of time,
my_recursive_function[a, b, MAX_DEPTH=1e9]
answered Nov 9, 2010 at 21:34
2
This is the closest to your code, and very unpythonic:
def recurse[folder_ids, count]:
folder_ids.append[folder.id]
for entry in child_folders:
folder_ids.append[entry.id]
child_folders_1 = getChildFolders[entry.id]
if count > 0:
recurse[folder_ids, count-1]
folder_ids = []
recurse[folder_ids, 4]
You should probably look for os.walk
and take a similar approach to walk the tree iteratively.
answered Nov 9, 2010 at 21:40
LloekiLloeki
6,4132 gold badges30 silver badges32 bronze badges
4
I needed something similar once to check a hierarchic tree. You could try:
def get_children_folders[self,mother_folder]:
'''
For a given mother folder, returns all children, grand children
[and so on] folders of this mother folder.
'''
folders_list=[]
folders_list.append[mother_folder]
for folder in folders_list:
if folder not in folders_list: folders_list.append[folder]
new_children = getChildFolders[folder.id]
for child in new_children:
if child not in folders_list: folders_list.append[child]
return folders_list
answered Sep 22, 2014 at 18:33
pedrovgppedrovgp
6758 silver badges23 bronze badges