flag - gcc options

Recurrencia de la cola en gcc/g++

Question

Intenté buscar, pero no pude encontrar: ¿cuáles son los requisitos para las funciones para que gcc optimice la recursividad de cola? ¿Hay alguna referencia o lista que contendría los casos más importantes? Como esta es una versión específica, mis intereses son 4.6.3 o versiones superiores (cuanto más nuevo mejor). Sin embargo, de hecho, cualquier referencia concreta sería muy apreciada.

¡Gracias por adelantado!

Answer 1

Con -O2 habilitado, gcc realizará la optimización de la cola de llamada, si es posible. Ahora, la pregunta es: ¿cuándo es posible?

Es posible eliminar una sola llamada recursiva siempre que la llamada recursiva ocurra inmediatamente antes o dentro de la declaración de return (única), por lo que no hay efectos secundarios observables después que no sea la devolución de un valor diferente. Esto incluye devolver expresiones que involucren al operador ternario.
Tenga en cuenta que incluso si hay varias llamadas recursivas en la expresión de retorno (como en el conocido ejemplo de Fibonacci: return (n==1) ? 1 : fib(n-1)+fib(n-2); ), la recursión de la llamada de la cola todavía se aplica, pero solo a la última llamada recursiva.

Como un caso especial obvio, si el compilador puede probar que la función recursiva (y sus argumentos) califica como expresión constante, puede (hasta una profundidad máxima de recursión configurable, por defecto 500) eliminar no solo la llamada final, sino la totalidad ejecución de la función. Esto es algo que GCC hace de manera rutinaria y confiable en -O2 , que incluso incluye llamadas a ciertas funciones de la biblioteca, como strlen en literales.