30

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?

Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
xax
  • 2,043
  • 4
  • 24
  • 28

5 Answers5

35

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

fortran
  • 74,053
  • 25
  • 135
  • 175
  • 1
    Is recursion then at all a viable approach in Python? Do most Python programmers avoid it? (i.e. is it un-Pythonic?) – xax Mar 08 '10 at 13:26
  • 4
    Tail recursion wouldn't help in this case since the recursive call is not the last operation in the function. – Judge Maygarden Mar 08 '10 at 13:32
  • 4
    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. – fortran Mar 08 '10 at 13:35
  • 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 Mar 08 '10 at 13:38
  • @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 Mar 08 '10 at 13:39
  • @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. – fortran Mar 08 '10 at 13:46
  • @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 Mar 08 '10 at 14:16
  • 2
    @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. – fortran Mar 08 '10 at 15:39
  • @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. – Judge Maygarden Mar 08 '10 at 20:17
  • @Judge good point, I'll update the answer to make that clearer – fortran Mar 09 '10 at 00:08
  • does stackless python not allow tail recursion? – jk. Mar 09 '10 at 14:58
  • wasn't sure about it, but indeed it does :-) – fortran Mar 09 '10 at 15:08
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.

Thiago Chaves
  • 9,218
  • 5
  • 28
  • 25
  • 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 Mar 08 '10 at 14:15
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.

Adrian
  • 2,123
  • 3
  • 18
  • 24
  • 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 Mar 08 '10 at 13:23
  • It is indeed. But you asked why your second one primeListRec didn't work. It's recursive, hence the recursion depth exceeded error. – Adrian Mar 08 '10 at 13:29
0

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.

Johannes Charra
  • 29,455
  • 6
  • 42
  • 51
-3

You can do it in a dirty way:

try: function() except: function()
Undo
  • 25,519
  • 37
  • 106
  • 129
Riptide00
  • 1