129 votos

¿Puede una función recursiva ser en línea?

 inline int factorial(int n)
{
    if(!n) return 1;
    else return n*factorial(n-1);
}
 

Mientras leía esta , encontró que el código anterior podría llevar a "infinito recopilatorio" si no se maneja por compilador correctamente.

¿Cómo funciona el compilador de decidir si una función en línea o no?

133voto

Derek Park Puntos 25025

En primer lugar, la inline de la especificación de una función es una sugerencia. El compilador puede (y a menudo lo hace), ignoran la presencia o ausencia de un inline calificador. Con eso dicho, un compilador puede en línea de una función recursiva, tanto como lo puede desenrollar un bucle infinito. Simplemente tiene que colocar un límite en el nivel al que se "desmarque" de la función.

Un compilador de optimización puede activar este código:

inline int factorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}

int f(int x)
{
    return factorial(x);
}

en este código:

int factorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}

int f(int x)
{
    if (x <= 1)
    {
        return 1;
    }
    else
    {
        int x2 = x - 1;
        if (x2 <= 1)
        {
            return x * 1;
        }
        else
        {
            int x3 = x2 - 1;
            if (x3 <= 1)
            {
                return x * x2 * 1;
            }
            else
            {
                return x * x2 * x3 * factorial(x3 - 1);
            }
        }
    }
}

En este caso, hemos básicamente entre líneas la función 3 veces. Algunos compiladores hacer realizar esta optimización. Recuerdo MSVC++ haber un ajuste para ajustar el nivel de alineaciones que se realizan en las funciones recursivas (hasta 20, creo).

22voto

Matt J Puntos 15475

De hecho, si el compilador no actuar de forma inteligente, puede intentar la inserción de copias de su inlined de la función de forma recursiva, creando infinitamente grande código. La mayoría de los compiladores modernos, se reconoce esto, sin embargo. Ellos pueden:

  1. No en línea de la función en todos los
  2. En línea hasta una cierta profundidad, y si no ha terminado por ese entonces, llame a la instancia independiente de su función utilizando la función estándar de la convención de llamada. Esto puede tomar la atención de muchos casos comunes en un alto rendimiento manera, dejando una de reserva para el caso raro con una gran profundidad de llamada. Esto también significa que usted mantenga ambas alineadas y separadas las versiones de que la función del código de su alrededor.

Para el caso 2, muchos compiladores han #pragmas puede configurar para especificar la profundidad máxima a la que debe hacer. En gcc, también puede pasar esto desde la línea de comandos con --max-inline-insns-recursive (ver más info aquí).

7voto

leppie Puntos 67289

Que yo sepa GCC hará eliminación llamada de cola en las funciones recursivas, si es posible. Su función no es sin embargo recursiva cola.

3voto

alex strange Puntos 892

Algunos recursivo funciones pueden ser transformadas en bucles, que efectivamente infinitamente inlines ellos. Creo que gcc puede hacer esto, pero no sé si otros compiladores.

1voto

mattlant Puntos 9136

El compilador hará un gráfico de llamadas para detectar este tipo de cosas y prevenirlos. Por lo que sería ver que la función se llama a sí mismo y no en línea.

Pero sobre todo es controlado por la palabra clave y del compilador interruptores en línea (Por ejemplo, se puede tener auto funciones inline pequeños, incluso sin la palabra clave.) Es importante señalar que las compilaciones de depuración nunca deben ser procesos en línea como la pila de llamadas no se conservará a espejo las llamadas que crearon en el código.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by: