peligro de funciones recursivas

A menudo la gente dice que no se recomienda usar funciones recursivas en Python (restricciones de profundidad de recursión, consumo de memoria, etc.)

Tomé un ejemplo de permutación de esta pregunta .

def all_perms(str): if len(str) <=1: yield str else: for perm in all_perms(str[1:]): for i in range(len(perm)+1): yield perm[:i] + str[0:1] + perm[i:] 

Luego lo transformé en una versión no recursiva (soy un novato de python)

 def not_recursive(string): perm = [string[0]] for e in string[1:]: perm_next = [] for p in perm: perm_next.extend(p[:i] + e + p[i:] for i in range(len(p) + 1)) perm = perm_next for p in perm: yield p 

Y los comparé

 before=time() print len([p for p in all_perms("1234567890")]) print "time of all_perms %i " % (time()-before) before=time() print len([p for p in not_recursive("1234567890")]) print "time of not_recursive %i " % (time()-before) before=time() print len([p for p in itertools.permutations("1234567890")]) print "time of itertools.permutations %i " % (time()-before) 

Los resultados son muy interesantes. La función recursiva es la más rápida 5 segundos, luego no recursiva 8 segundos, luego se acumula 35 segundos.

¿Entonces las funciones recursivas son tan malas en Python? ¿Qué hay de malo con las itertols.permutations integradas?

La recursión es “mala” en Python porque generalmente es más lenta que una solución iterativa y porque la profundidad de la stack de Python no es ilimitada (y no hay una optimización de llamadas de cola). Para una función de sum, sí, es probable que desee una profundidad ilimitada, ya que sería perfectamente razonable querer sumr una lista de un millón de números, y el delta de rendimiento se convertirá en un problema con una cantidad tan grande de elementos. En ese caso no debes usar la recursividad.

Por otra parte, si está caminando por un árbol DOM leído desde un archivo XML, es poco probable que supere la profundidad de recursión de Python (1000 de forma predeterminada). Ciertamente podría, pero en la práctica, probablemente no lo hará. Cuando sepa con qué tipo de datos estará trabajando con anticipación, puede estar seguro de que no desbordará la stack.

Una caminata de árbol recursiva es, en mi opinión, mucho más natural de escribir y leer que una iterativa, y la sobrecarga de recursión es generalmente una pequeña parte del tiempo de ejecución. Si realmente te importa que tomes 16 segundos en lugar de 14, lanzar PyPy podría ser un mejor uso de tu tiempo.

La recursión parece un ajuste natural para el problema que publicaste y si crees que el código es más fácil de leer y mantener de esa manera, y el rendimiento es el adecuado, entonces hazlo.

Crecí escribiendo códigos en computadoras que, en la práctica, limitaban la profundidad de la recursión a aproximadamente 16, si se proporcionaba, por lo que 1000 me parece lujoso. 🙂

La recursión es buena para los problemas que se prestan para implementaciones limpias, claras y recursivas. Pero como toda la progtwigción, debe realizar un análisis de algoritmo para comprender las características de rendimiento. En el caso de recursión, además del número de operaciones, también debe estimar la profundidad máxima de stack.

La mayoría de los problemas ocurren cuando los nuevos progtwigdores asumen que la recursión es mágica y no se dan cuenta de que hay una stack debajo que lo hace posible. También se sabe que los nuevos progtwigdores asignan memoria y nunca la liberan, y otros errores, por lo que la recursión no es única en este peligro.

Tus tiempos están completamente equivocados:

 def perms1(str): if len(str) <=1: yield str else: for perm in perms1(str[1:]): for i in range(len(perm)+1): yield perm[:i] + str[0:1] + perm[i:] def perms2(string): perm = [string[0]] for e in string[1:]: perm_next = [] for p in perm: perm_next.extend(p[:i] + e + p[i:] for i in range(len(p) + 1)) perm = perm_next for p in perm: yield p s = "01235678" import itertools perms3 = itertools.permutations 

Ahora pruébalo con timeit:

 thc:~$ for i in 1 2 3; do echo "perms$i:"; python -m timeit -s "import permtest as p" "list(p.perms$i(ps))"; done perms1: 10 loops, best of 3: 23.9 msec per loop perms2: 10 loops, best of 3: 39.1 msec per loop perms3: 100 loops, best of 3: 5.64 msec per loop 

Como puede ver, itertools.permutations es, con mucho, el más rápido, seguido por la versión recursiva.

Pero tanto la función Python pura no tuvo la oportunidad de ser rápida, ya que realizan operaciones costosas como agregar listas ala perm[:i] + str[0:1] + perm[i:]

No puedo reproducir los resultados de la sincronización (en Python 2.6.1 en Mac OS X):

 >>> import itertools, timeit >>> timeit.timeit('list(all_perms("0123456789"))', ... setup='from __main__ import all_perms'), ... number=1) 2.603626012802124 >>> timeit.timeit('list(itertools.permutations("0123456789"))', number=1) 1.6111600399017334