Python: Przekroczono maksymalną głębokość rekurencji

85

Mam następujący kod rekursji, w każdym węźle wywołuję zapytanie sql, aby uzyskać węzły należące do węzła nadrzędnego.

tutaj jest błąd: 

Exception RuntimeError: 'maximum recursion depth exceeded' in <bound method DictCursor.__del__ of <MySQLdb.cursors.DictCursor object at 0x879768c>> ignored

RuntimeError: maximum recursion depth exceeded while calling a Python object
Exception AttributeError: "'DictCursor' object has no attribute 'connection'" in <bound method DictCursor.__del__ of <MySQLdb.cursors.DictCursor object at 0x879776c>> ignored

Metoda, którą wywołuję, aby uzyskać wyniki sql:

def returnCategoryQuery(query, variables={}):
    cursor = db.cursor(cursors.DictCursor);
    catResults = [];
    try:
        cursor.execute(query, variables);
        for categoryRow in cursor.fetchall():
            catResults.append(categoryRow['cl_to']);
        return catResults;
    except Exception, e:
        traceback.print_exc();

Właściwie nie mam żadnego problemu z powyższą metodą, ale i tak postawiłem to, aby dać właściwy przegląd pytania.

Kod rekursji:

def leaves(first, path=[]):
    if first:
        for elem in first:
            if elem.lower() != 'someString'.lower():
                if elem not in path:
                    queryVariable = {'title': elem}
                    for sublist in leaves(returnCategoryQuery(categoryQuery, variables=queryVariable)):
                        path.append(sublist)
                        yield sublist
                    yield elem

Wywołanie funkcji rekurencyjnej 

for key, value in idTitleDictionary.iteritems():
    for startCategory in value[0]:
        print startCategory + " ==== Start Category";
        categoryResults = [];
        try:
            categoryRow = "";
            baseCategoryTree[startCategory] = [];
            #print categoryQuery % {'title': startCategory};
            cursor.execute(categoryQuery, {'title': startCategory});
            done = False;
            while not done:
                categoryRow = cursor.fetchone();
                if not categoryRow:
                    done = True;
                    continue;
                rowValue = categoryRow['cl_to'];
                categoryResults.append(rowValue);
        except Exception, e:
            traceback.print_exc();
        try:
            print "Printing depth " + str(depth);
            baseCategoryTree[startCategory].append(leaves(categoryResults))
        except Exception, e:
            traceback.print_exc();

Kod do wydrukowania słownika, 

print "---Printing-------"
for key, value in baseCategoryTree.iteritems():
    print key,
    for elem in value[0]:
        print elem + ',';
    raw_input("Press Enter to continue...")
    print

Jeśli rekurencja jest zbyt głęboka, powinienem otrzymywać błąd, kiedy wywołuję moją funkcję rekurencyjną, ale kiedy otrzymuję ten błąd podczas drukowania słownika.

python recursion max depth tree-traversal dodaj średniki
źródło
8
Przepisz go iteracyjnie zamiast rekurencyjnie.
Seth Carnegie,
1
if first:Wyboru jest zbędne z for elem in first:. Jeśli zapytanie zwróci pustą listę wyników, iteracja po niej po prostu, poprawnie nie zrobi nic, tak jak sobie tego życzysz. Możesz także utworzyć tę listę w prostszy sposób, używając zrozumienia listy (a te średniki są niepotrzebne i ogólnie uważane za brzydkie :))
Karl Knechtel,
@KarlKnechtel przepraszam za średniki, czy możesz powiedzieć, że dopiero zaczynam programować w Pythonie .... :)
dodaj średniki
Nie ma potrzeby przepraszać, w końcu nie płacę Ci za pisanie tego :) Mam nadzieję, że uznasz Pythona za wyzwalające;)
Karl Knechtel

Odpowiedzi:

162

Możesz zwiększyć dozwoloną głębokość stosu - dzięki temu możliwe będą głębsze rekurencyjne wywołania, na przykład:

import sys
sys.setrecursionlimit(10000) # 10000 is an example, try with different values

... Ale radziłbym najpierw spróbować zoptymalizować swój kod, na przykład używając iteracji zamiast rekurencji.

Óscar López
źródło
1
Dodałem linię zamiast 10000 dodałem 30000, ale skończyło się na usterce segmentacji (porzucono rdzeń) :(
dodaj średniki
16
Jest powód, dla którego jest ustawiony na 1000 ... Myślę, że Guido van Rossum powiedział coś na ten temat .
Lambda Fairy
3
Argumentem Guido jest więc to, że prawidłowe wywołanie ogona (1) zapewnia gorsze ślady stosu - w przeciwieństwie do braku ramek, gdy piszesz je iteracyjnie? jak to jest gorsze? (2) Jeśli damy im coś miłego, mogą zacząć na tym polegać. (3) Nie wierzę w to, pachnie jak Scheme. (4) Python jest źle zaprojektowany, więc kompilator nie może skutecznie wykryć, czy coś jest wywołaniem końcowym. Myślę, że możemy się zgodzić?
John Clements,
1
@hajef Po trzecie, ogonowe wywoływanie z pewnością nie dotyczy tylko list; każda struktura drzewa wygrywa. Spróbuj przejść przez drzewo bez rekurencyjnych wywołań w pętli; kończysz ręcznie modelując stos. Wreszcie, twój argument, że Python nigdy nie został zaprojektowany w ten sposób, jest z pewnością prawdziwy, ale niewiele robi, aby mnie przekonać, że jest to projekt boga.
John Clements
1
Tylko dlatego, że van Rossum ma w swojej masce pszczołę dotyczącą rekurencji, nie oznacza, że ​​rekursja zamiast iteracji nie jest „optymalna”: zależy od tego, co optymalizujesz!
Gene Callahan