Funciones recursivas, desbordamientos de pila y combinadores en Y

Question

Tengo una función recursiva (en C #) que necesito llamar unas 800 millones de veces;obviamente, esto normalmente resultaría en un desbordamiento de pila después de la llamada número 900.He eliminado esto en varios bucles, pero el patrón recursivo es mucho más fácil y más limpio de mantener.

Estoy buscando implementar la función recursiva usando un combinador y, a partir de lo que estoy leyendo y visto, eso debería resolver el problema de desbordamiento de pila y arreglar los múltiples bucles anidados.

¿Alguien tiene experiencia en el uso del combinador y?¿Seguiré atrapado en un desbordamiento de pila?

Tome el ejemplo simple de un factorial.Un factorial en la mayoría de los números mayor que 5000 provocará un desbordamiento de pila.Si usara un combinador y correctamente en ese escenario, ¿arreglaría el desbordamiento de la pila?

No parece trivial de implementar, así que quiero confirmarlo antes de dedicar el esfuerzo de desarrollo / recursos a implementar y aprender el combinador y.

Answer 1

No, usar el combinador Y no ayudará en su situación.Si necesita hacer algo 800 millones de veces, puede (a) recurrir o (b) repetir (o supongo que (c) escribir 800 millones de llamadas a su función).Dado que el combinador Y no se repite, debe repetirse.

Lo que está buscando es un bucle, a menos que esté utilizando un entorno de ejecución que ofrezca una recursividad de cola adecuada (como Scheme).

Dicho esto, implementar el combinador Y desde cero en el idioma que elija es un ejercicio excelente.

Answer 2

Los combinadores Y son útiles, pero creo que realmente quieres optimización de recursividad de cola que elimine el uso de la pila para funciones recursivas de cola.La recursividad de cola solo es posible cuando el llamador devuelve inmediatamente el resultado de cada llamada recursiva y nunca ningún cálculo adicional después de la llamada.Desafortunadamente, C # no admite la optimización de la recursividad de la cola; sin embargo, puedes emularla con un trampolín que permite una conversión simple del método recursivo de la cola a un método envuelto en trampolín.

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}

Answer 3

Puedes usar el trampolín como se usa en Reactive Extension, he intentado explicarlo en mi blog http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Una solución es convertir su (s) función (es) para usar un ciclo y una estructura de datos explícita contexto . El contexto representa lo que la gente generalmente considera la pila de llamadas. Puede encontrar mi respuesta a otra pregunta sobre la conversión a la recursividad de cola útil. Los pasos relevantes son del 1 al 5; 6 y 7 son específicos para esa función en particular, mientras que la tuya suena más complicada.

Sin embargo, la alternativa "fácil" es agregar un contador de profundidad a cada una de sus funciones; cuando alcanza algún límite (determinado por la experimentación), genera un nuevo hilo para continuar la recursión con una pila nueva. El hilo antiguo se bloquea esperando que el hilo nuevo le envíe un resultado (o si quieres ser elegante, un resultado o una excepción para volver a subir). El contador de profundidad vuelve a 0 para el nuevo hilo; cuando llegue al límite, cree un tercer hilo y así sucesivamente. Si almacena subprocesos en caché para evitar pagar el costo de creación de subprocesos con más frecuencia de lo necesario, con suerte obtendrá un rendimiento aceptable sin tener que reestructurar drásticamente su programa.