Python recursive function error: "maximum recursion depth exceeded" [duplicate]

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

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