Python中的递归循环函数

我有一个数据库，它将一个文件夹关系建模为n层嵌套。对于任何给定的文件夹，我想生成所有子文件夹的列表。Python中的递归循环函数

假设我有一个名为“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)

来源

2010-11-09 andyashton

您确定要排除所有子级别，无论他们居住的级别是什么级别吗？ – delnan 2010-11-09 21:39:43

递归函数是一个很好的办法做到这一点：

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

来源

2010-11-09 21:39:10

谢谢，这（除其他外）做我所需要的。 – andyashton 2010-11-09 22:10:02

请注意Python中的递归限制很低 – Falmarri 2010-11-09 22:46:47

请参阅'sys.getrecursionlimit（）'和'sys.setrecursionlimit（limit）'..默认限制为1000，但您可以稍微设置一下。它不会崩溃，直到我的机器上的8000 ;-) – 2010-11-09 23:21:16

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)

来源

2010-11-09 21:34:38

在n级递归之后停止通常只会给你一个错误/不完整的结果。只要递归到你完成了 - 如果堆栈溢出，那就把它变成迭代。或者，如果您确实需要限制递归深度，请引发适当的异常。 – delnan 2010-11-09 21:37:44

@delnan：提问者问如何在指定深度后停止递归。我同意这通常是一个坏主意 - 因此，为什么你可以传递像MAX_DEPTH这样的1e9，这实际上是无限的。 – 2010-11-10 08:15:25

这是最接近你的代码，很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并采用类似的方法迭代地遍历树。

来源

2010-11-09 21:40:39 Lloeki

我也会提示'os.walk'，但他没有走文件系统，他有一个奇怪的“在数据库中的文件系统”或其他东西。 – delnan 2010-11-09 21:42:32

看到了。更正以反映我的真正含义。 – Lloeki 2010-11-09 21:44:09

'os。walk'是递归的，而不是迭代的（我确认了源代码）。 – delnan 2010-11-09 21:48:13

我通常避免像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在没有子女时返回空列表。如果它做了其他事情，比如返回一个定位值或者引发一个异常，那么就必须进行修改。

来源

2010-11-09 21:43:57 aaronasterling

[我明白你在那里做了什么]（https://www.youtube.com/watch?v=8X_Ot0k4XJc）。 – 2016-12-29 13:13:35

我需要类似的东西来检查分层树。您可以尝试：

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

来源

2014-09-22 18:33:22 pedrovgp

Python中的递归循环函数

回答

相关问题