Python recursive function error: "maximum recursion depth exceeded"

Question

I solved Problem 10 of Project Euler with the following code, which works through brute force:

def isPrime(n):

    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True


def primeList(n):

    primes = []

    for i in range(2,n):
        if isPrime(i):
            primes.append(i)

    return primes


def sumPrimes(primelist):
    prime_sum = sum(primelist)
    return prime_sum


print (sumPrimes(primeList(2000000)))

The three functions work as follows:

1. isPrime checks whether a number is a prime;
2. primeList returns a list containing a set of prime numbers for a certain range with limit 'n', and;
3. sumPrimes sums up the values of all numbers in a list. (This last function isn't needed, but I liked the clarity of it, especially for a beginner like me.)

I then wrote a new function, primeListRec, which does exactly the same thing as primeList, to help me better understand recursion:

def primeListRec(i, n):
    primes = []
    #print i


    if (i != n):
        primes.extend(primeListRec(i+1,n))

    if (isPrime(i)):
        primes.append(i)
        return primes


    return primes

The above recursive function worked, but only for very small values, like '500'. The function caused my program to crash when I put in '1000'. And when I put in a value like '2000', Python gave me this:

RuntimeError: maximum recursion depth exceeded.

What did I do wrong with my recursive function? Or is there some specific way to avoid a recursion limit?

Solution 1

Recursion is not the most idiomatic way to do things in Python, as it doesn't have tail recursion optimization thus making impractical the use of recursion as a substitute for iteration (even if in your example the function is not tail-recursive, that wouldn't help anyway). Basically, that means that you shouldn't use it for things that have a complexity greater than linear if you expect your inputs to be large, (still it's OK for doing things that have a logarithmic recursion depth, like divide and conquer algorithms as QuickSort).

If you want to try that approach, use a language better suited to do functional programming, as Lisp, Scheme, Haskell, OCaml, etc.; or give a try to Stackless Python, that has broader limits in stack usage and also has tail recursion optimisation :-)

By the way, a tail-recursive equivalent of your function could be:

def primeList(n, i=2, acc=None):
    return i > n and (acc or []) or primeList(n, i+1, (acc or []) + (isPrime(i) and [i] or []))

Another "by the way", you shouldn't construct a list if you're using it just to add up the values... The Pythonic way to solve Project Euler's 10th problem is:

print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))

(OK, maybe splitting it in various lines would be even more Pythonic, but I love one liners ^_^)

Solution 2

Like already said, in languages that can't deal with deep stacks it's better to take an iterative approach. In your case, in particular, it's best to change the algorithm used. I suggest using the Sieve of Eratosthenes to find the list of prime numbers. It will be quite faster than your current program.

Solution 3

Well I'm no python expert but I presume you've hit the stack limit. That's the problem with recursion, it's great when you don't have to recurse very many times but no good when the number of recursions gets even moderately big.

The ideal alternative is to rewrite your algorithm to use iteration instead.

Edit: Actually having looked closer your specific error you can get past it by changing sys.getrecursionlimit. That'll only take you so far though. Eventually you'll get a stackoverflow exception which brings me back to my original point.

Comments

[xax]

I don't quite understand. Wasn't the first algorithm, i.e. 'primeList', already based on iteration? Also, the question uses a value of 2 million; is this an unreasonable limit to expand to?

[xax]

Is recursion then at all a viable approach in Python? Do most Python programmers avoid it? (i.e. is it un-Pythonic?)

[Adrian]

It is indeed. But you asked why your second one primeListRec didn't work. It's recursive, hence the recursion depth exceeded error.

[Judge Maygarden]

Tail recursion wouldn't help in this case since the recursive call is not the last operation in the function.

[fortran]

It's a viable approach when the iterative version would need a stack anyway (e.g. traversing a tree, producing permutations, etc.) and the recursion depth is bounded to a reasonable size. In this case you're trying to use recursion in an artificial manner, as it was clearly a for loop what you needed.

[xax]

I didn't know what "tail recursion" was, so I hit Google, and found out that there are also other types of recursion. That's new to me; I thought there was only one kind of recursion. Thank you! But I still must ask: what would be a Pythonic way to deal with recursion involving large numbers, if any?

[xax]

So must I always stick to manual iterations via for/while loops for large numbers?

[fortran]

@Judge I wasn't saying that it would help here (although the function could be rewritten easily to be tail recursive), just that it's the reason why recursion is not idiomatic in Python.

[fortran]

@user283169 in Python you will always eventually hit the stack limit if you nest a large enough number of function calls, even if they are tail recursive.

[Johannes Charra]

Yes, I think so ... not totally sure, though. There may be exceptions to the rule, but I cannot clearly distinguish them. :)

[xax]

Indeed, my program is slow. Took more than a minute to complete, which breaks Project Euler's "one minute rule". I've just looked into the Sieve of Eratosthenes approach, and it's fascinating. I'll try my best to learn it. Thank you for the suggestion.

[xax]

@fortran: So I'm guessing that Python really isn't a language for heavy-duty recursion? Is that what you're trying to say?

[xax]

I'll definitely look for the exceptions you mentioned. Thanks!

[fortran]

@user283169 I'm trying to say exactly what I say: recursion shouldn't be abused in Python. If you need it because your problem is recursive in nature, use it, but don't try to replace iteration with recursion because that's not the way it's meant to be used.

[Judge Maygarden]

@fortran I didn't mean to imply that you were unaware of how tail recursion works. My intention was to avoid confusion for other readers since your answer makes it sound like tail-call optimizations are an issue in this particular case.

[fortran]

@Judge good point, I'll update the answer to make that clearer

[jk.]

does stackless python not allow tail recursion?

[fortran]

wasn't sure about it, but indeed it does :-)

[Admin]

ok, i take that back