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?

Answer 1

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.

Answer 2

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 ^_^)

Answer 3

You're iterating over n numbers and recursing at each step. Therefore Python's recursion limit defines your maximum input number. That's obviously undesirable. Especially because the Euler problems typically deal with pretty large numbers.

Answer 4

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.