Funciones recursivas, desbordamientos de pila e Y-Combinators

Question

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

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

¿Alguien tiene experiencia con el y-combinator? ¿Todavía estaré atrapado en un desbordamiento de pila?

Tome el ejemplo simple de un factorial. Un factorial en la mayoría de los números más grandes que como 5,000 causará un desbordamiento de la pila. Si utilicé un combinador y correctamente en ese escenario, ¿solucionaría el desbordamiento de la pila?

No parece trivial de implementar, por lo que quiero confirmarlo antes de gastar el esfuerzo/recursos de desarrollo implementando y aprendiendo el y-combinator.

Answer 1

No, usar el Y-combinator no ayudará a su situación. Si necesita hacer algo 800 millones de veces, puede (a) repetir, o (b) repetir (o supongo que (c) escribir 800 millones de llamadas a su función). Como el Y-combinator no gira, debe recurrirse.

Un bucle es lo que está buscando, a menos que esté utilizando un entorno de tiempo de ejecución que ofrezca recursividad final adecuada (como Scheme).

Habiendo dicho eso, implementar el Y-combinator desde cero en el idioma de su elección es un ejercicio excelente.

Answer 2

Y los combinadores son útiles, pero creo que realmente desea la optimización de recursión de cola que elimina el uso de la pila para las funciones recursivas de cola. La recursividad de cola solo es posible cuando el resultado de cada llamada recursiva es devuelto inmediatamente por la persona que llama al y nunca se realiza ningún cálculo adicional después de la llamada. Desafortunadamente C# no es compatible con la optimización de la recursividad de la cola, sin embargo, se puede emular con un trampolín que permite una conversión simple de 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

Puede usar cama elástica que se usa en Reactivo de extensión, que han tratado de explicar en mi blog http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Una solución consiste en convertir su función (s) para utilizar un bucle y una explícita contexto estructura de datos. El contexto representa lo que la gente generalmente considera como la pila de llamadas. Puede encontrar my answer to another question about converting to tail recursion útil. Los pasos relevantes son de 1 a 5; 6 y 7 son específicos para esa función particular, mientras que los tuyos suenan más complicados.

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