recursividad infinita en Python o lenguajes dinámicos

Question

Recientemente he intentado compilar el programa algo como esto con GCC:

int f(int i){ 
    if(i<0){ return 0;} 
    return f(i-1); 
f(100000); 

y corrió muy bien. Cuando inspeccioné los marcos de la pila, el compilador optimizó el programa para usar solo un cuadro, volviendo al principio de la función y solo reemplazando los argumentos a f. Y - el compilador ni siquiera se ejecutaba en modo optimizado.

Ahora, cuando intento lo mismo en Python, alcanzo la pared de recursividad máxima (o probablemente desborde la pila si establezco una profundidad de recursión demasiado alta).

¿Existe alguna manera de que un lenguaje dinámico como python pueda aprovechar estas bonitas optimizaciones? Tal vez sea posible usar un compilador en lugar de un intérprete para que esto funcione.

¡Solo curiosidad!

Answer 1

La optimización de la que habla es conocida como eliminación de llamada final: una llamada recursiva se desarrolla en un bucle iterativo.

Ha habido una cierta discusión de esto, pero la situación actual es que esto no se agregará, al menos a cpython propiamente dicho. Ver Guido's blog entry para una discusión. No hay somedecorators que manipulan la función para realizar esta optimización. Por lo general, solo obtienen el ahorro de espacio, no el tiempo (de hecho, en general son más lentos)

Answer 2

No tiene nada que ver con el hecho de que es un lenguaje dinámico o que se interpreta. CPython simplemente no implementa Tail Recursion optimización. Puede encontrar que JPython, etc.

Answer 3

Cuando inspeccionó los marcos de pila el compilador optimizado el programa para utilizar sólo un marco, con sólo saltando hacia atrás hasta el principio de la función y sólo la sustitución de los argumentos para f.

Lo que estás describiendo se llama "recursividad de cola". Algunos compiladores/intérpretes lo admiten, otros no. La mayoría no lo hace, de hecho. Como habrás notado, gcc sí. Y, de hecho, la recursividad de cola es una parte de la especificación para el lenguaje de programación Scheme, por lo que todos los compiladores/intérpretes Scheme deben admitir recurrencia de cola. Por otro lado, los compiladores para lenguajes como Java y Python (así como la mayoría de los otros idiomas, apostaría) no hacen recursividad de cola.

¿Existe algún modo de que un lenguaje dinámico como python pueda aprovechar estas bonitas optimizaciones?

Cómo que ahora , o lo preguntas en términos más abstractos? Hablando en abstracto, ¡sí! Sería absolutamente posible que los lenguajes dinámicos aprovechen la recursión de cola (Scheme, por ejemplo). Pero hablando concretamente, no, CPython (el intérprete canónico de Python) no tiene un indicador u otro parámetro para habilitar la recursividad final.