Python recursive function error: "maximum recursion depth exceeded"

Posted by user283169 on Stack Overflow See other posts from Stack Overflow or by user283169
Published on 2010-03-08T13:10:12Z Indexed on 2010/03/08 13:36 UTC
Read the original article Hit count: 679

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?

© Stack Overflow or respective owner

Related posts about beginner

Related posts about python