Python error función recursiva: "profundidad de recursión máximo excedido"

Question

I resuelto el problema 10 de Proyecto Euler con el siguiente código, que trabaja a través de la fuerza bruta:

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

Las tres funciones funcionan como sigue:

1. isPrime comprueba si un número es primo;
2. primeList devuelve una lista que contiene un conjunto de números primos para un cierto intervalo con un límite de 'n', y;
3. sumPrimes resume los valores de todos los números en una lista. (No es necesario Esta última función, pero me gusta la claridad de la misma, sobre todo para un principiante como yo.)

Entonces escribí una nueva función, primeListRec, que hace exactamente lo mismo que primeList, para ayudar a comprender mejor la recursividad:

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 

La función recursiva anteriormente trabajó, pero sólo para valores muy pequeños, como '500'. La función provocó que mi programa fallara cuando coloqué '1000'. Y cuando puse un valor como '2000', Python me dio esto:

RuntimeError: la profundidad máxima de recursión superó.

¿Qué hice mal con mi función recursiva? ¿O hay alguna forma específica de evitar un límite de recursión?

Answer 1

La recursividad no es la forma más idiomática de hacer cosas en Python, ya que no tiene optimización tail recursion, lo que hace poco práctico el uso de recursión como sustituto de la iteración (incluso si en su ejemplo la función no es recursiva , eso no ayudaría de todos modos). Básicamente, eso significa que no debes usarlo para cosas que tienen una complejidad mayor que la lineal si esperas que tus entradas sean grandes (aún está bien para hacer cosas que tienen una profundidad de recursión logarítmica, como los algoritmos de división y conquista como QuickSort)

Si quieres probar este enfoque, utilizar un lenguaje más adecuado para hacer la programación funcional, como Lisp, Scheme, Haskell, OCaml, etc.; o darle una oportunidad a Stackless Python, que tiene límites más amplios en el uso de la pila y también tiene la optimización de recursión de cola :-)

Por cierto, un equivalente de cola recursiva de la función podría ser:

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 [])) 

otro "por cierto", no debería construir una lista si se está usando sólo para sumar los valores ... la forma Pythonic para resolver el problema del décimo Proyecto Euler es:

print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1))) 

(OK, tal vez dividirlo en varias líneas sería aún más pitónico, pero me encantan los liners^_ ^)

Answer 2

Bueno, yo soy un experto pitón pero presumen que has alcanzado el límite stack. Ese es el problema con la recursión, es genial cuando no tienes que recurrir muchas veces, pero no es bueno cuando el número de recurrencias es incluso moderadamente grande.

La alternativa ideal es reescribir su algoritmo para usar iteración en su lugar.

Edit: En realidad habiendo mirado más de cerca su error específico puede pasarlo cambiando sys.getrecursionlimit. Sin embargo, eso solo te llevará tan lejos. Eventualmente obtendrás una excepción de stackoverflow que me devuelve a mi punto original.

Answer 3

Está iterando en n números y recurriendo en cada paso. Por lo tanto, el límite de recursión de Python define su número máximo de entrada. Eso es obviamente indeseable. Especialmente porque los problemas de Euler generalmente se relacionan con números bastante grandes.

Answer 4

Como ya se dijo, en los idiomas que no pueden tratar con stacks profundos, es mejor adoptar un enfoque iterativo. En su caso, en particular, es mejor cambiar el algoritmo utilizado. Sugiero usar el Sieve of Eratosthenes para encontrar la lista de números primos. Será bastante más rápido que tu programa actual.

Answer 5

Puede hacerlo de una manera sucia:

try: function() except: function()