Рекурсивная циклическая функция в Python

Question

У меня есть база данных, которая моделирует отношение папок к n уровням вложенности.Для любой данной папки я хочу создать список всех дочерних папок.

Если у меня есть функция с именем getChildFolders(), какой самый эффективный способ вызвать этот тип рекурсивного цикла?

Следующий код работает для 4 уровней вложенности, но я бы хотелнапример, больше гибкости в определении глубины рекурсии или в умной остановке цикла, когда больше нет дочерних элементов для отслеживания.

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)

Answer 1

Рекурсивная функция - хороший способ сделать это:

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

Answer 2

Я обычно избегаю рекурсии, как чума в python, потому что она медленная и из-за ошибки переполнения стека.

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

Это предполагает, что getChildFolders возвращает пустой список, когда нет дочерних элементов.Если он делает что-то еще, например возвращает значение часового или выдает исключение, то необходимо будет внести изменения.

Answer 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)

Answer 4

Мне нужно было нечто подобное один раз, чтобы проверить иерархическое дерево.Вы можете попробовать:

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

Answer 5

Это самый близкий к вашему коду и очень непифонный:

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)

Вероятно, вам следует поискать os.walk и использовать аналогичный подход для многократного обхода дерева.