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中的遞歸循環函數

回答

相關問題