Python: Maximum recursion depth exceeded

Question

I have the following recursion code, at each node I call sql query to get the nodes belong to the parent node.

here is the error:

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

Method that I call to get sql results:

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();

I actually don't have any issue with the above method but I put it anyways to give proper overview of the question.

Recursion Code:

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

Calling the recursive function

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();

Code to print the dictionary,

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

If the recursion is too deep I should be getting the error when I call my recursion function, but when I get this error when I print the dictionary.

The `if first:` check is redundant with `for elem in first:`. If the query returns an empty result list, then iterating over it will simply, correctly do nothing, as you desire. Also, you can create that list more simply with a list comprehension (and those semicolons are unnecessary and generally considered ugly :) ) — Karl Knechtel, Nov 18 '11 at 03:46
@KarlKnechtel sorry about the semicolons, can you tell I am just getting into Python programming.... :) — add-semi-colons, Nov 18 '11 at 05:07
No need to apologize, I'm not paying you to write it after all :) I hope you find Python liberating ;) — Karl Knechtel, Nov 18 '11 at 05:52

score 178 · Accepted Answer · answered Nov 18 '11 at 03:10

178

You can increment the stack depth allowed - with this, deeper recursive calls will be possible, like this:

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

... But I'd advise you to first try to optimize your code, for instance, using iteration instead of recursion.

answered Nov 18 '11 at 03:10

Óscar López

232,561
37
312
386

I am getting the error when I try to print if the recursive is too deep I should be getting the error when I call my recursive function. Because down the line I call this function and save the results in a dictionary and when I try to print that dictionary i get this error. I have updated the code. – add-semi-colons Nov 18 '11 at 05:01
1

I added the line instead of 10000 i added 30000 but I ended up Segmentation Fault (core dumped) :( – add-semi-colons Nov 18 '11 at 14:45
Thanks I fixed the problem, created a dictionary to keep track of every element and avoided any loop. And combination of of increasing the recursion limit and avoiding loop i think its working... Thanks for the help again. – add-semi-colons Nov 18 '11 at 17:14
19

There's a reason why it's set at 1000... I believe [Guido van Rossum said something about this](http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html). – Lambda Fairy Nov 28 '11 at 04:43
@LambdaFairy It is interesting to hear some criticism of the approach of trying to solve all by recursion and what are the downsides of optimizing the languages for it. – user7610 Nov 11 '13 at 11:28
+1 haha this is hilarious, I just had the pleasure of implementing the deepest recursive backtracking ever. Thanks! – salezica Mar 29 '14 at 07:46
4

So Guido's argument is that proper tail calling (1) provides worse stack traces---as opposed to no frames at all when you write it iteratively? how is that worse? (2) If we give them something nice, they might start relying on it. (3) I don't believe in it, it smells like Scheme. (4) Python is badly designed, so that a compiler can't efficiently discover whether something is a tail call. I guess that one we can agree on? – John Clements Mar 12 '17 at 01:58
@John Clements I learned programming using racket's TRE and I miss it but you wouldn't implement infix operators or get rid of brackets in a lisp language if I asked you, would you? I could really use TRE for my current project but understand his argumentation. 1) Python means clearness and that includes stacktraces. 2) If we opened an optional bypass, skillfull and nooby programmers would use tham in unexpacted ways - see 1. 3) TRE is a mighty tool to handle linked lists that are not present in Python. Python has other ways to do most of TRE's job and 4) was never designed to TRE. – hajef May 29 '17 at 12:02
1

@hajef Your comments are friendly! So when I disagree with each of them, please don't take it the wrong way. First, you refer to functional languages with infix operators and no parens: see Haskell and ML, two popular functional languages with infix operators and no parens. Second, you suggest that "clearness includes stacktraces"; if you want stack traces, you can certainly enable them in a properly tail-calling language, either by keeping a fixed number of frames, or by keeping all call traces--whatever you want. The point is that in a properly tail-calling language, you're not *forced* to. – John Clements May 30 '17 at 06:15
3

@hajef Third, tail-calling is certainly not just for lists; any tree structure wins. Try traversing a tree without recursive calls in a loop; you wind up modeling the stack by hand. Finally, your argument that Python was never designed this way is certainly true, but does little to convince me that it's a god design. – John Clements May 30 '17 at 06:18
@John Clements Just yesterday I tryed to scale my recursive graph parsing program to thousands instead of hundreds of nodes and 2 things happened: 1) The code run for some miutes 2) It hit the 1000 max. recursion depth. Setting mrd to 1500 it run 30 min. than gave me what little I wanted. I made the recusive part a for loop what is almost exactly the same but looks better. I never came across a problem where it happened to be much of a difference if I use TRE or for - what I would just call the python equivalent of TRE now. The problem with my programm was a O(n) "operation" - hidden nesting. – hajef May 30 '17 at 11:04
1

@hajef That's not surprising; I conjecture that loops are already "baked into" your worldview. I'm teaching a data structures class, and the students are running into this limit *all the time*. Appending two lists, summing the numbers in a list, etc. etc. In all of these cases, lifting the limit partially alleviates the problem, but the real solution is to eliminate the artificial penalty associated with tail-calling. – John Clements May 30 '17 at 23:02
@JohnClements I'd like to discuss this further but we are getting off topic/ quite chatty here. As I get from meta posts there is still no way to trigger a chat with imported coments but we don't need them. I tried to follow [this](https://meta.stackoverflow.com/a/313538/7967942) answer but it seems I don't have the required privilege. At least the named button is not there for me, I only can search messages or ignore. – hajef May 31 '17 at 07:01
3

Just because van Rossum has a bee in his bonnet about recursion doesn't mean recursion instead of iteration is not "optimal": depends on what you are optimizing! – Gene Callahan Oct 27 '17 at 13:02
This just created more problems for me. – Edward B. May 22 '20 at 19:45
I'm sorry. :( It's Friday at the end of the day and I'm working on an aggravating python script I was hoping to have done this week. And it's actually not my algorithm acting up, either, but the pyyaml library getting a stack overflow. It's completely out of my control to fix being part of that library and I'm going to have write my own parser now. Thank you for your solution, though. It didn't work for me but for others writing their own algorithms it should. – Edward B. May 22 '20 at 21:18

Python: Maximum recursion depth exceeded

1 Answers1

Linked