c# - recursiva - recursividad ejemplos
¿Por qué.NET/C#no se optimiza para la recursividad de la cola de llamada? (5)
C # no se optimiza para la recursión de la cola de cola porque ¡para eso es F #!
Para conocer con detalle las condiciones que impiden que el compilador de C # realice optimizaciones de llamadas de cola, consulte este artículo: Condiciones de JIT CLR tail-call .
Interoperabilidad entre C # y F #
C # y F # interoperan muy bien, y debido a que .NET Common Language Runtime (CLR) está diseñado con esta interoperabilidad en mente, cada lenguaje está diseñado con optimizaciones que son específicas para su intención y propósitos. Para un ejemplo que muestra cuán fácil es llamar al código F # del código C #, vea Llamar al código F # del código C # ; para un ejemplo de invocación de funciones C # del código F #, consulte Funciones de llamada C # desde F # .
Para la interoperabilidad de delegados, consulte este artículo: Delegar interoperabilidad entre F #, C # y Visual Basic .
Diferencias teóricas y prácticas entre C # y F #
Aquí hay un artículo que cubre algunas de las diferencias y explica las diferencias de diseño de la recursividad de cola entre C # y F #: Generación de código de operación de llamada y cola en C # y F # .
Aquí hay un artículo con algunos ejemplos en C #, F # y C ++ / CLI: Adventures in Tail Recursion en C #, F # y C ++ / CLI
La principal diferencia teórica es que C # está diseñado con bucles, mientras que F # está diseñado según los principios del cálculo Lambda. Para un muy buen libro sobre los principios del cálculo Lambda, vea este libro gratuito: Estructura e Interpretación de Programas de Computación, por Abelson, Sussman y Sussman .
Para ver un artículo introductorio muy bueno sobre las llamadas de cola en F #, consulte este artículo: Introducción detallada a las llamadas de cola en F # . Finalmente, aquí hay un artículo que cubre la diferencia entre la recursividad sin cola y la recurrencia de la cola (en F #): recurrencia de la cola vs. recurrencia sin cola en F sharp .
Encontré esta pregunta sobre qué idiomas optimizan la recursividad de cola. ¿Por qué C # no optimiza la recursividad de cola, siempre que sea posible?
Para un caso concreto, ¿por qué este método no está optimizado en un bucle ( Visual Studio 2008 32 bits, si eso importa) ?:
private static void Foo(int i)
{
if (i == 1000000)
return;
if (i % 100 == 0)
Console.WriteLine(i);
Foo(i+1);
}
Este envío de comentarios de Microsoft Connect debe responder a su pregunta. Contiene una respuesta oficial de Microsoft, así que recomiendo pasar por eso.
Gracias por la sugerencia. Consideramos emitir instrucciones de llamada final en varios puntos del desarrollo del compilador de C #. Sin embargo, hay algunos problemas sutiles que nos han obligado a evitar esto hasta el momento: 1) En realidad, hay un costo indirecto no trivial para usar la instrucción .tail en el CLR (no es solo una instrucción de salto, ya que las llamadas finales finalmente se vuelven en muchos entornos menos estrictos, como entornos de tiempo de ejecución de lenguaje funcional donde las llamadas finales están muy optimizadas). 2) Hay pocos métodos C # reales en los que sería legal emitir llamadas finales (otros idiomas fomentan patrones de codificación que tienen más recursividad de cola, y muchos que dependen en gran medida de la optimización de llamadas finales realmente realizan una reescritura global (como las transformaciones de Continuing Passing) ) para aumentar la cantidad de recursividad de cola). 3) En parte debido a 2), los casos en que los métodos C # apilan el desbordamiento debido a una recursión profunda que debería haber tenido éxito son bastante raros.
Dicho todo esto, continuamos observando esto, y es posible que en una versión futura del compilador encontremos algunos patrones en los que tenga sentido emitir instrucciones .tail.
Por cierto, como se ha señalado, vale la pena señalar que la recursividad de cola se optimiza en x64.
La compilación de JIT es un acto de equilibrio engañoso entre no pasar demasiado tiempo haciendo la fase de compilación (lo que ralentiza considerablemente las aplicaciones de corta duración) versus no hacer suficiente análisis para mantener la aplicación competitiva a largo plazo con una compilación anticipada estándar. .
Curiosamente, los pasos de compilación de NGen no están destinados a ser más agresivos en sus optimizaciones. Sospecho que esto es porque simplemente no quieren tener errores donde el comportamiento depende de si el JIT o NGen fue responsable del código de la máquina.
El CLR sí admite la optimización de llamadas finales, pero el compilador específico del idioma debe saber cómo generar el opcode relevante y el JIT debe estar dispuesto a respetarlo. F#''s fsc de F#''s generará los códigos de operación relevantes (aunque para una recursión simple puede simplemente convertir todo en un ciclo while directamente). C # ''s csc no.
Consulte esta publicación en el blog para obtener más información (posiblemente ahora esté desactualizada debido a los cambios recientes de JIT). Tenga en cuenta que el CLR cambia para 4.0 x86, x64 e ia64 lo respetará .
Puede usar la técnica de trampolín para funciones recursivas de cola en C # (o Java). Sin embargo, la mejor solución (si solo le interesa la utilización de la pila) es usar este pequeño método de ayuda para envolver partes de la misma función recursiva y hacerla iterativa mientras se mantiene la función legible.
Recientemente me dijeron que el compilador de C # para 64 bits optimiza la recursividad de cola.
C # también implementa esto. La razón por la que no siempre se aplica es que las reglas que se usan para aplicar la recursión de cola son muy estrictas.