Рекурсивная циклическая функция в 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

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 3

Это ближайший к вашему коду, и очень 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) 

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

Answer 4

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

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 5

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

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