recursive - Error de la función recursiva de Python: "se excedió la profundidad máxima de recursión"

recursiveness python

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cuál es la profundidad máxima de recursión en Python y cómo aumentarla? 14 respuestas

Resolví el problema 10 del proyecto Euler con el siguiente código, que funciona 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 de la siguiente manera:

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 rango con límite ''n'', y;
3. sumPrimes resume los valores de todos los números en una lista. (Esta última función no es necesaria, pero me gustó su claridad, especialmente para un principiante como yo).

Luego escribí una nueva función, primeListRec , que hace exactamente lo mismo que primeList , para ayudarme a comprender mejor la recursión:

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 anterior funcionó, pero solo para valores muy pequeños, como ''500''. La función hizo que mi programa se bloquee cuando coloco en ''1000''. Y cuando puse un valor como ''2000'', Python me dio esto:

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

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

Answer 1

Bueno, no soy un experto en python, pero supongo que has alcanzado el límite de stack . Ese es el problema con la recursión, es genial cuando no tienes que repetir muchas veces, pero no es bueno cuando la cantidad de recursiones se vuelve moderadamente grande.

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

Edición: En realidad, habiendo examinado más de cerca su error específico, puede sys.getrecursionlimit cambiando sys.getrecursionlimit . Eso solo te llevará muy lejos. Eventualmente obtendrás una excepción de stackoverflow que me regresa a mi punto original.

Answer 2

Como ya se dijo, en idiomas que no pueden lidiar con acumulaciones profundas, es mejor adoptar un enfoque iterativo. En su caso, en particular, es mejor cambiar el algoritmo utilizado. Sugiero usar el Tamiz de Eratóstenes para encontrar la lista de números primos. Será bastante más rápido que tu programa actual.

Answer 3

Estás iterando sobre 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 tratan con números bastante grandes.

Answer 4

La recursión no es la forma más idiomática de hacer cosas en Python, ya que no tiene una optimización de recursión de cola , por lo que no es práctico el uso de la recursión como sustituto de la iteración (incluso si en su ejemplo la función no es recursiva de cola, eso no no ayuda de todos modos). Básicamente, eso significa que no debe usarlo para cosas que tienen una complejidad mayor que la lineal si espera que sus entradas sean grandes, (aún así está bien para hacer cosas que tengan una profundidad de recursión logarítmica, como dividir y conquistar algoritmos como QuickSort ).

Si desea probar ese enfoque, utilice un lenguaje más adecuado para realizar la programación funcional, como Lisp, Scheme, Haskell, OCaml, etc .; o pruebe con Stackless Python, que tiene límites más amplios en el uso de pilas y también tiene optimización de recursión de cola :-)

Por cierto, un equivalente recursivo de la cola de su 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ías construir una lista si la estás usando solo para sumar los valores ... La manera Pythonic de resolver el problema número 10 del 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)))

(De acuerdo, tal vez dividirlo en varias líneas sería aún más Pythonic, pero me encanta uno de los liners ^ _ ^)

Answer 5

Puedes hacerlo de una manera sucia:

try: function() except: function()