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