10

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)
Improve this question
1
  • You sure you want to out all subdirs, regardless of at what level in the hierachy they live, into a flat list? Commented Nov 9, 2010 at 21:39

5 Answers 5

Reset to default
12

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
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thanks, this (among others) does what I need.
See sys.getrecursionlimit() and sys.setrecursionlimit(limit) .. the default limit is 1000, but you can set it up a bit. It doesnt crash till 8000 on my machine ;-)
The inner function idiom, which is useful in many languages, is unnecessary in Python because you have default arguments.
@Joe: That's not true, the point of the outer function is bottle it up and have a clean definition, documentation and a simpler recursive function. Especially since I'd need a default argument of [], which you can't write down directly in the definition.
Re: clean definition - The normal calling convention is no dirtier for a single def, and the inner function definition is still there being dirty when there's two. Exposing the recursion-related parameters can also make co-recursive idioms simpler. Re: default argument - If I'm writing functional code (and if I'm writing recursively, I am), I wouldn't modify an argument I'm passed, but return a new value when called. I'd probably do that procedurally in most cases too.
|
8

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.

Improve this answer

1 Comment

I see what you did there.
3 
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)
Improve this answer

2 Comments

Stopping after n levels of recursion usually just gives you a wrong/incomplete result. Just recurse until you are done - if the stack overflows, well, turn it into iteration. Or if you really have to limit the recursion depth, throw an appropriate exception.
@delnan: Well, the questioner asked how to stop the recursion after a specified depth. I agree it's usually a bad idea - hence why you can pass something like 1e9 as MAX_DEPTH, which is effectively unlimited.
0

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.

Improve this answer

4 Comments

I was going to suggest os.walk too, but he isn't walking the filesystem, he has a weird "filesystem in a database" or something.
Saw that. Corrected to reflect what I really meant.
os.walk is recursive, not iterative (I checked the source to be sure).
So it implements recursion under cover of iteration... Oh, the irony.
0

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
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.