Python recursive function error: "maximum recursion depth exceeded"
python, recursion
Solution
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 ^_^)
Problem
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: - isPrime checks whether a number is a prime; - primeList returns a list containing a set of prime numbers for a certain range with limit 'n', and; - 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?