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.

Solution

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.

Comments

[add-semi-colons]

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]

I added the line instead of 10000 i added 30000 but I ended up Segmentation Fault (core dumped) :(

[add-semi-colons]

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.

[Lambda Fairy]

There's a reason why it's set at 1000... I believe Guido van Rossum said something about this.

[user7610]

@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.

[slezica]

+1 haha this is hilarious, I just had the pleasure of implementing the deepest recursive backtracking ever. Thanks!

[John Clements]

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?

[hajef]

@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.

[John Clements]

@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]

@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.

[hajef]

@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.

[John Clements]

@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.

[hajef]

@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 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.

[Gene Callahan]

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!

[Edward B.]

This just created more problems for me.

[Edward B.]

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.