¿Qué tan segura es la recursión en Python?

Estoy trabajando en una tarea de AI, y a pesar de las sugerencias de mi profesor, no tengo ninguna intención de escribir esta tarea en voz alta. Sin embargo, quiero escribirlo de forma recursiva, para mantenerlo conciso y simple. Aquí está mi pregunta:

¿Estoy corriendo un mayor riesgo de quedarme sin espacio en la stack si realizo una búsqueda en un espacio de estado grande? ¿Qué tan profundo es el montón de Python?

¿Qué tan profundo es el montón de Python?

El límite de recursión predeterminado en Python es de 1000 cuadros. Puede usar sys.setrecursionlimit(n) para cambiar eso a su propio riesgo.

Si está configurado para usar python, sugeriría usar un patrón más adecuado para el idioma. Si desea utilizar la búsqueda de estilo recursivo y necesita una profundidad de stack arbitraria, puede utilizar los generadores mejorados de Python (coroutines) para crear un “patrón de trampolín” (hay un ejemplo en PEP342 )

y a pesar de las sugerencias de mi profesor, no tengo ninguna intención de escribir esta tarea en voz baja

Si el ejercicio está pensado para ser basado en la recursión, un lenguaje optimizado para la llamada de la cola, como un lisp, es probablemente su mejor apuesta.

La recursión en Python (CPython, es decir) no puede ir más allá de sys.getrecursionlimit() . Puede establecer este límite en un valor diferente con sys.setrecursionlimit .

Veo tres opciones:

  1. Después de todo, use Lisp, está optimizado para problemas recursivos (y los comstackdores Lisp inteligentes eliminarán la recursión de cola)
  2. Establezca el límite de recursión en la función recursiva para obtener una recursión ilimitada (a riesgo de que el progtwig coma la muerte en llamas )
  3. Usa la iteración con una stack explícita. Una simple list servirá. append es empujar, pop es pop
 >>> i=0 >>> def a(): ... global i ... i += 1 ... try: ... a() ... except: ... print(i) ... >>> a() 999 >>> import sys >>> sys.getrecursionlimit() 1000 

No estoy seguro si eso ayuda

Python limita la profundidad de la recursión a un valor que puede averiguar llamando a sys.getrecursionlimit y cambiando llamando a sys.setrecursionlimit. El valor predeterminado no es terriblemente grande. Si lo configuras demasiado alto, entonces puedes terminar haciendo estallar la stack de C cuando Python recurre. El nivel de “demasiado alto” depende de la plataforma, aunque el valor predeterminado debe ser seguro (se obtiene una excepción de Python en lugar de una falla) en todas las plataformas.

Hay lenguajes que hacen fuertes garantías sobre la optimización de llamadas de cola. El esquema es el ejemplo más conocido; Es un dialecto Lisp. Debería considerar aprender al menos un lenguaje similar al Lisp, sin importar cuánto le disguste a su profesor.

Como han señalado otros, puede boost la profundidad de la recursión usando sys.setrecursiondepth() , aunque a riesgo de desbordar la stack de C (suponiendo que esté usando CPython). Si se encuentra con este problema, puede crear un hilo con un tamaño de stack mayor llamando a thread.stack_size() con el nuevo tamaño de stack, y luego generar un nuevo hilo para hacer el trabajo real.