language agnostic - ventajas - ¿Cómo maneja tu lenguaje favorito la recursión profunda?

sintaxis de recursividad

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 se apresura a señalar que siempre se pueden convertir las funciones recursivas a iterativas y que siempre son más rápidas. Eso es 100% cierto. No es de lo que se trata mi pregunta).

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.

Lo intenté 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 aplana casos triviales, pero segfaults en más complicados, o eso me dicen.]

Usé estas funciones 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 sobre cómo otros lenguajes (por ejemplo, PHP, Ruby, Java, Lua, Ocaml, Haskell) manejan la recursividad y por qué lo 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

"La gente de Python se apresura a señalar que siempre se pueden convertir las funciones recursivas a iterativas y que siempre son más rápidas"

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 pueda verse lo más simple posible? (Digo esto para no implementar implementadores de Python, sino porque la respuesta explica el problema).

Las optimizaciones de la recursión 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 la cola en iteraciones: básicamente, se logra detectando que es posible, es decir, que la función se puede reorganizar de modo 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 molestarse en guardar todo eso. 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 la gente de Python, la conversión de una función recursiva general a una iteración no es trivial: por ejemplo, si es multiplicativamente recursiva, entonces, en un enfoque simple, aún 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 que llegue 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

C # /. NET utilizará 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 implementará la recursión final en algunos casos .

Shri Borde también tiene una publicación sobre este tema . Por supuesto, el CLR cambia continuamente, y con .NET 3.5 y 3.5SP1 puede haber cambiado nuevamente con respecto a las llamadas finales.

Answer 3

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

Eso fue con una pila (-Xss) de 300Mo.

Con una opción -server , eso podría aumentarse.

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

Answer 4

Ejecutando ruby ​​1.9.2dev (revisión de 2010-07-11 28618) [x86_64-darwin10.0.0] en un macbook blanco antiguo:

def f
  @i += 1
  f
end

@i = 0

begin
  f
rescue SystemStackError
  puts @i
end

saca 9353 para mí, lo que significa que Ruby craps con menos de 10,000 llamadas en la pila.

Con recursión cruzada, como:

def f
  @i += 1
  g
end

def g
  f
end

Craps en la mitad del tiempo, en 4677 (~ = 9353/2).

Puedo exprimir algunas iteraciones más envolviendo la llamada recursiva en un proceso:

def f
  @i += 1
  yield
end

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

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

que llega a 4850 antes de salir el error.

Answer 5

En algunos casos no patológicos (como el suyo), (más reciente) Lua utilizará recursión de llamada de cola , 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 probó la recursividad cruzada (f llamando a g y g llamando a f ...).

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

Answer 6

Esta es más una pregunta de implementación que una pregunta 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 se apresura a señalar que siempre se pueden convertir las funciones recursivas a iterativas y que siempre son más rápidas. Eso es 100% cierto. No es de lo que se trata mi pregunta).

Quizás dicen eso, pero esto no es del todo correcto. La recursión siempre se puede convertir a iteración, pero a veces también requiere el uso manual de una pila . 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 7

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

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

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

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

  } else {
    return $_[0]
  }
}

Cuando se 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 puede usar el 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 8

PHP tiene un límite predeterminado de 100 antes de morir:

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

Editar: puede cambiar el límite con ini_set(''xdebug.max_nesting_level'', 100000); , pero si supera las 1150 iteraciones, PHP se bloquea:

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

Answer 9

Soy bastante entusiasta de la programación funcional, y dado que la mayoría de esos lenguajes implementan la optimización de llamadas de cola, puede recurse tanto como desee :-P

Sin embargo, prácticamente, tengo 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, sino principalmente como un ejercicio de parcheo dinámico de código de bytes Python y aprender más acerca de las partes internas de Pythons. Aquí hay algunos enlaces interesantes: http://lambda-the-ultimate.org/node/1331 y http://www.rowehl.com/blog/?p=626

Answer 10

Usando lo siguiente en la consola interactiva F #, se ejecutó 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;;

Luego probé una traducción directa, es decir,

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

g 0 100000000;;

Mismo resultado pero compilación diferente.

Esto es lo que se ve 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 el compilador F # represente de manera diferente dos funciones que son fundamentalmente iguales. 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 11

Visual Dataflex apilará desbordamiento.

Answer 12

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