Rekursive looping-Funktion in Python

Ich habe eine Datenbank, die Modelle einer foldering Beziehung zu n Ebenen verschachteln. Für jeden beliebigen Ordner, ich möchte erstellen Sie eine Liste aller untergeordneten Ordner.

Angenommen ich habe eine Funktion namens getChildFolders(), was ist der effizienteste Weg, um Anruf dieser Art rekursive Schleife?

Der folgende code funktioniert für die 4 Ebenen verschachteln, aber ich möchte mehr Flexibilität bei der entweder die Angabe der Tiefe der Rekursion, oder in intelligent beenden die Schleife, wenn es keine Kinder mehr zu Folgen.

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)

Sie sicher, dass Sie alle Unterverzeichnisse, unabhängig davon, auf welcher Ebene der Hierarchie Sie Leben, in eine flache Liste?

InformationsquelleAutor andyashton | 2010-11-09

3

Einer rekursiven Funktion ist ein schöner Weg, um dies zu tun:
```
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
```
Danke, das (unter anderem) das tut, was ich brauche.
Beachten Sie die rekursive Grenze in python ist sehr gering
Sehen sys.getrecursionlimit() und sys.setrecursionlimit(limit) .. der Standardwert ist 1000, aber Sie können es ein wenig. Es tut Absturz bis 8000 auf meinem Rechner 😉
Die innere Funktion idiom, was nützlich ist, in vielen Sprachen, ist überflüssig in Python, weil Sie Standard-Argumente.
Das stimmt nicht, der Punkt der äußeren Funktion mit der Flasche it up und haben eine saubere definition, Dokumentation und eine einfachere rekursive Funktion. Vor allem, da bräuchte ich ein Standard-argument von [], das können Sie nicht, schreiben Sie direkt in die definition.

InformationsquelleAutor Jochen Ritzel
3

Ich generell vermeiden, Rekursion wie die Pest in python, weil es langsam und da der ganze stack-überlauf-Fehler-Sache.
```
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
```
Dies setzt Voraus, dass getChildFolders gibt eine leere Liste zurück, wenn es keine Kinder. Wenn es nicht etwas anderes, wie die Rückkehr einer sentinel-Wert oder eine Ausnahme auslösen, dann änderungen vorgenommen werden müssen.

ich sehe was du da gemacht hast.

InformationsquelleAutor aaronasterling

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)

Beenden nach n Stufen der Rekursion in der Regel nur vermittelt Sie ein Falsches/unvollständiges Ergebnis. Nur Durchlaufen, bis Sie fertig sind - wenn der stack überläuft, gut, schalten Sie ihn in die iteration. Oder wenn Sie wirklich müssen zur Begrenzung der Rekursionstiefe, werfen eine entsprechende Ausnahme.
Gut, der Fragesteller fragte, wie zu stoppen die Rekursion nach einer bestimmten Tiefe. Ich Stimme zu, es ist in der Regel eine schlechte Idee - also warum können Sie so etwas wie 1e9 als MAX_DEPTH, die ist praktisch unbegrenzt.

InformationsquelleAutor

0

Dies ist die am nächsten zu Ihrem code, und sehr 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)
```
Sollten Sie sich wahrscheinlich für os.walk und nehmen einen ähnlichen Ansatz, um zu Fuss den Baum iterativ.

Ich wollte vorschlagen os.walk auch, aber er ist nicht zu Fuß, das Dateisystem, er hat ein komisches "Dateisystem in einer Datenbank" oder so etwas.
Sah, dass. Korrigiert um zu reflektieren, was ich eigentlich meinte.
os.walk ist rekursiv, nicht iterativ (ich habe die Quelle um sicher zu sein).
So ist es implementiert Rekursion unter dem Deckmantel der iteration... Oh, die Ironie.

InformationsquelleAutor Lloeki

Brauchte ich etwas ähnliches einmal zu überprüfen, eine hierarchische Struktur. Sie könnten versuchen:

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

InformationsquelleAutor pedrovgp

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.