Fonction de bouclage récursif en Python

Question

J'ai une base de données qui modélise une relation de dossier à n niveaux d'imbrication. Pour un dossier donné, je veux générer une liste de tous les dossiers enfants.

En supposant que j'ai une fonction appelée "getChildFolders()", quel est le moyen le plus efficace d'appeler ce type de boucle récursive. Le code suivant fonctionne pour 4 niveaux d'imbrication, mais j'aimerais plus de flexibilité pour spécifier la profondeur de récursion ou pour arrêter intelligemment la boucle quand il n'y a plus d'enfants à suivre.

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

Une fonction récursive est une bonne façon de le faire:

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

Ceci est le plus proche de votre code, et très 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) 

Vous devriez probablement chercher os.walk et prendre une approche similaire pour marcher l'arbre itérativement.

Answer 4

J'évite généralement la récursion comme la peste en python car elle est lente et à cause de toute l'erreur d'overflow de pile.

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 

Cela suppose que getChildFolders retourne une liste vide quand il n'y a pas d'enfants. S'il fait quelque chose d'autre, comme retourner une valeur sentinelle ou déclencher une exception, alors des modifications devront être faites.

Answer 5

J'avais besoin de quelque chose de similaire une fois pour vérifier un arbre hiérarchique. Vous pouvez essayer:

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