¿Cómo maneja su idioma favorito la recursión profunda?

Question

Recientemente comencé a aprender Python y me sorprendió bastante encontrar un límite de recursión de 1000 de profundidad (por defecto). Si lo configura lo suficientemente alto, alrededor de 30000, se bloquea con un error de segmentación como C. Aunque, C parece ir bastante más alto.

(La gente de Python son rápidos en señalar que se puede convertir siempre funciones recursivas a los iterativos y que son siempre más rápido. Eso es 100% verdad. No es realmente lo que mi pregunta es acerca de embargo.)

Probé el mismo experimento en Perl y alrededor de 10 millones de recursiones consumió todos mis 4 gigas de ram y usé^C para dejar de intentarlo. Claramente, Perl no usa la pila C, pero usa una cantidad ridícula de memoria cuando recurre, no terriblemente impactante considerando cuánto trabajo tiene que hacer para llamar a las funciones.

Probé en Pike y me sorprendió por completo obtener 100,000,000 recursiones en aproximadamente 2 segundos. No tengo idea de cómo lo hizo, pero sospecho que aplastó la recursión a un proceso iterativo, no parece consumir memoria extra mientras lo hace. [Nota: Pike hace aplanar casos triviales, pero segfaults en los más complicados, o eso me han dicho.]

que utilizan estas funciones de otro modo inútiles:

int f(int i, int l) { if(i<l) return f(i+1,l); return i; } 

sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] }; 

def f(i,l): 
    if i<l: 
    return f(i+1,l) 
    return i 

Tengo mucha curiosidad de cómo otros idiomas (por ejemplo, PHP, Ruby, Java, Lua, Ocaml, Haskell) manejan la recursividad y por qué la manejan de esa manera. Además, tenga en cuenta si hace una diferencia si la función es "recursiva de cola" (ver comentario).

Answer 1

"gente El Python son rápidos en señalar que se puede convertir siempre funciones recursivas a los iterativos y que son siempre más rápido"

Esto es cierto, pero si es realmente tan fácil como todo eso, ¿por qué Python no lo hace por mí, para que mi código se vea lo más simple posible? (Digo esto para no implementar implementadores de Python, sino porque la respuesta explica el problema).

Las optimizaciones de la recursividad han estado presentes en los lenguajes funcionales desde, por ejemplo, el siglo XIV o algo así. Las implementaciones de Haskell, CAML, Lisp típicamente convierten al menos las funciones recursivas de cola en iteraciones: básicamente haces esto detectando que es posible, es decir, que la función se puede reorganizar de manera que no se utilicen variables locales distintas del valor de retorno después de la llamada recursiva. . Un truco para hacer posible si se realiza algún trabajo con el valor de retorno recursado antes del retorno, es introducir un parámetro adicional de "acumulador". En términos simples, esto significa que el trabajo se puede hacer efectivamente en el camino "hacia abajo" en lugar de hacia "arriba": busca "cómo hacer que una función sea recursiva" para obtener más detalles.

Los detalles reales de convertir una función recursiva de la cola en un bucle es básicamente conectar con su convención de llamadas para que pueda "realizar la llamada" simplemente configurando los parámetros y volviendo al inicio de la función, sin molestar para guardar todas esas cosas en el alcance que sabes que nunca usarás. En términos de ensamblador, no tiene que conservar registros de llamadas guardadas si el análisis de flujo de datos indica que no se utilizan más allá de la llamada, y lo mismo ocurre con cualquier elemento de la pila: no es necesario mover el puntero de la pila en una llamada si no le importa que "su" bit de pila quede garabateado en la siguiente recursión/iteración.

Contrariamente a cómo parafraseó a los usuarios de Python, la conversión de una función recursiva general a una iteración no es trivial: por ejemplo, si es multiplicativamente recursiva, en un enfoque simple, todavía necesitaría una pila.

La memorización es una técnica útil, sin embargo, para funciones arbitrariamente recursivas, que le gustaría buscar si le interesan los posibles enfoques. Lo que significa es que cada vez que se evalúa una función, se pega el resultado en un caché. Para usar esto para optimizar la recursión, básicamente, si su función recursiva cuenta "hacia abajo", y la memoriza, entonces puede evaluarla iterativamente agregando un ciclo que cuenta "arriba" calculando cada valor de la función sucesivamente hasta llegar al objetivo. Esto utiliza muy poco espacio de pila siempre que el memo cache sea lo suficientemente grande como para contener todos los valores que necesitará: por ejemplo, si f (n) depende de f (n-1), f (n-2) y f (n -3) solo necesita espacio para 3 valores en la memoria caché: a medida que sube, puede echar la escalera. Si f (n) depende de f (n-1) yf (n/2), necesita mucho espacio en la memoria caché, pero aún menos de lo que usaría para la pila en una recursión no optimizada.

Answer 2

PHP tiene un límite predeterminado de 100 antes de que muera:

Fatal error: Maximum function nesting level of '100' reached, aborting!

Editar: Se puede cambiar el límite con ini_set('xdebug.max_nesting_level', 100000);, pero si vas por encima de unos 1.150 accidentes de iteraciones PHP:

[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.

Answer 3

De acuerdo con este hilo, around 5,000,000 con java, 1Gb de RAM. (y eso, con la versión 'cliente' del hotspot)

Eso fue con un stack (-Xss) de 300Mo.

Con un -server option, eso se puede aumentar.

También se puede intentar optimizar el compilador (with JET por ejemplo) para reducir la sobrecarga de la pila en cada capa.

Answer 4

C# /. NET usará recursividad de cola en un conjunto particular de circunstancias. (El compilador de C# no emite un código de operación tailcall, pero el JIT will implement tail recursion in some cases.

Sri Borde also has a post on this topic. Por supuesto, el CLR está cambiando continuamente, y con .NET 3.5 y 3.5SP1 que puede haber cambiado de nuevo con respecto a la cola llamadas.

Answer 5

Visual Dataflex apilará desbordamiento.

Answer 6

En algunos casos no patológicos (como su), (última) Lua utilizará tail call recursion, es decir. saltará sin presionar los datos en la pila. Entonces, el número de ciclos de recursión puede ser casi ilimitado.

probado con:

function f(i, l) 
    if i < l then 
     return f(i+1, l) 
    end 
    return i 
end 

local val1 = arg[1] or 1 
local val2 = arg[2] or 100000000 
print(f(val1 + 0, val2 + 0)) 

También con:

function g(i, l) 
    if i >= l then 
     return i 
    end 
    return g(i+1, l) 
end 

e incluso intentó transversal de recursión (f llamando g y g llamando f ...).

En Windows, Lua 5.1 usa alrededor de 1.1MB (constante) para ejecutar esto, finaliza en unos pocos segundos.

Answer 7

Utilizando el siguiente en la consola interactiva F #, se corrieron en menos de un segundo:

let rec f i l = 
    match i with 
    | i when i < l -> f (i+1) l 
    | _ -> l 

f 0 100000000;; 

entonces intentaron una traducción recta es decir

let rec g i l = if i < l then g (i+1) l else l 

g 0 100000000;; 

mismo resultado pero diferente compilación.

Esto es lo que f se ve como en cuando se traduce a C#:

int f(int i, int l) 
{ 
    while(true) 
    { 
    int num = i; 
    if(num >= l) 
     return l; 
    int i = num; 
    l = l; 
    i = i + 1; 
    } 
} 

g, sin embargo se traduce a esto:

int g(int i, int l) 
{ 
    while(i < l) 
    { 
    l = l; 
    i++; 
    } 
    return l; 
} 

Es interesante que dos funciones que son fundamentalmente, el compilador F # representa de manera diferente lo mismo. También muestra que el compilador F # tiene una optimización recursiva de cola. Por lo tanto, esto debería repetirse hasta que llegue al límite de enteros de 32 bits.

Answer 8

Esto es más una cuestión de implementación que una cuestión de idioma. No hay nada que impida que un implementador de compilador de C (stoopid) también limite su pila de llamadas a 1000. Hay muchos procesadores pequeños por ahí que no tendrían espacio en la pila incluso para muchos.

(La gente de Python son rápidos en señalar que se puede convertir siempre funciones recursivas a los iterativos y que son siempre más rápido. Eso es 100% verdad. No es realmente lo que mi pregunta es acerca de embargo.)

Quizás dicen eso, pero esto no es del todo correcto. La recursividad siempre se puede convertir a iteración, pero a veces también requiere el uso manual de una pila también. En esas circunstancias, podría ver que la versión recursiva es más rápida (suponiendo que es lo suficientemente inteligente como para hacer optimizaciones simples, como sacar declaraciones innecesarias fuera de la rutina recursiva). Después de todo, la pila empuja las llamadas a procedimientos circundantes son un problema bien delimitado que su compilador debería saber cómo optimizar muy bien. Las operaciones de pila manual, por otro lado, no van a tener un código de optimización especializado en su compilador, y es probable que tengan todo tipo de controles de cordura en la interfaz del usuario que tomarán ciclos adicionales.

Puede ser que la solución iterativa/de pila sea siempre más rápida en Python. Si es así, eso es un error de Python, no de recursión.

Answer 9

Hay una manera de mejorar el código Perl, para hacer que use una pila de tamaño constante. Para ello, utiliza un formulario especial de goto.

sub f{ 
    if($_[0] < $_[1]){ 

    # return f($_[0]+1, $_[1]); 

    @_ = ($_[0]+1, $_[1]); 
    goto &f; 

    } else { 
    return $_[0] 
    } 
} 

Cuando lo llame por primera vez asignará espacio en la pila. Luego cambiará sus argumentos y reiniciará la subrutina, sin agregar nada más a la pila. Por lo tanto, pretenderá que nunca se llamó a sí mismo, convirtiéndolo en un proceso iterativo.

---

También podría utilizar el módulo Sub::Call::Recur. Lo que hace que el código sea más fácil de entender y más corto.

use Sub::Call::Recur; 
sub f{ 
    recur($_[0]+1, $_[1]) if $_[0] < $_[1]; 
    return $_[0]; 
} 

Answer 10

Estoy muy fan de la programación funcional, y puesto que la mayoría de esos langauges implementar la optimización de llamada de cola, puede recursivo tanto como te gusta :-P

Sin embargo, en la práctica, lo tiene que usar mucho Java y también usar Python. No tengo idea de qué límite tiene Java, pero para Python había planeado (pero aún no lo había hecho) implementar un decorador que optimizara la función decorada. Estaba planeando esto para no optimizar la recursión, pero principalmente como un ejercicio en el parcheo dinámico de bytecode de Python y aprender más sobre las partes internas de Pythons. Heres algunos enlaces itneresting: http://lambda-the-ultimate.org/node/1331 y http://www.rowehl.com/blog/?p=626

Answer 11

Operando 1.9.2dev rubí (2010-07-11 revisión 28618) [x86_64-darwin10.0.0] en un MacBook blanco mayor:

def f 
    @i += 1 
    f 
end 

@i = 0 

begin 
    f 
rescue SystemStackError 
    puts @i 
end 

salidas para 9353 yo, es decir, Ruby craps con menos de 10,000 llamadas en la pila.

Con transversal recursión, tales como:

def f 
    @i += 1 
    g 
end 

def g 
    f 
end 

que dados a cabo en la mitad del tiempo, en 4677 (~ = 9353/2).

puedo exprimir un poco más iteraciones envolviendo la llamada recursiva en un proc:

def f 
    @i += 1 
    yield 
end 

@i = 0 
@block = lambda { f(&@block) } 

begin 
    f(&@block) 
rescue SystemStackError 
    puts @i 
end 

la que se levanta a 4850 antes de erroring a cabo.

Answer 12

clojure proporciona una forma especial para la recursividad de la cola "recurrente" esto solo se puede utilizar en los lugares de la cola del ast. De lo contrario, se comporta como java y es probable que arroje una StackverflowException.