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当没有孩子时返回一个空列表。如果它执行其他操作，例如返回标记值或引发异常，则必须进行修改。