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

Question

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

Como estaba leyendo this, encontré que el código anterior conduciría a una "compilación infinita" si el compilador no lo maneja correctamente.

¿Cómo decide el compilador si desea alinear una función o no?

Answer 1

En primer lugar, la especificación inline de una función es solo una pista. El compilador puede (y a menudo lo hace) ignorar por completo la presencia o ausencia de un calificador inline. Dicho esto, un compilador puede alinear una función recursiva, del mismo modo que puede desenrollar un bucle infinito. Simplemente tiene que establecer un límite en el nivel al que "desenrollará" la función.

Un compilador de optimización podría convertir 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 la función inline 3 veces. Algunos compiladores hacen realizar esta optimización. Recuerdo que MSVC++ tenía una configuración para ajustar el nivel de alineación que se realizaría en las funciones recursivas (hasta 20, creo).

Answer 2

El compilador creará un gráfico de llamadas para detectar este tipo de cosas y evitarlas. Entonces vería que la función se llama a sí misma y no en línea.

Pero principalmente está controlado por la palabra clave en línea y los modificadores del compilador (Por ejemplo, puede tenerlo en línea incorporando pequeñas funciones incluso sin la palabra clave.) Es importante tener en cuenta que las compilaciones de depuración nunca deberían estar en línea ya que la callstack no conservarse para reflejar las llamadas que creó en el código.

Answer 3

De hecho, si su compilador no actúa de forma inteligente, puede tratar de insertar copias de su función inline d recursivamente, creando código infinitamente grande. La mayoría de los compiladores modernos reconocerán esto, sin embargo. Se puede:

1. no coloca en línea de la función en absoluto
2. en línea que hasta una cierta profundidad, y si no ha terminado para entonces, llamar a la instancia independiente de su función usando la función estándar de convención de llamada . Esto puede ocuparse de muchos casos comunes de una manera de alto rendimiento, mientras que deja una alternativa para el caso raro con una gran profundidad de llamada. Esto también significa que tiene guardadas versiones impresas y separadas del código de esa función.

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

Answer 4

El compilador crea un gráfico de llamadas; cuando se detecta un ciclo invocando a sí mismo, la función ya no se inline después de cierta profundidad (n = 1, 10, 100, cualquiera que sea el sintonizador del compilador).

Answer 5

"¿Cómo decide el compilador si alinea una función o no?"

Eso depende del compilador, las opciones que se especificaron, el número de versión del compilador, tal vez la cantidad de memoria disponible, etc.

código fuente del programa todavía tiene que obedecer las reglas para funciones inline . Ya sea que la función esté incorporada o no, debe prepararse para la posibilidad de que esté en línea (un número desconocido de veces).

La declaración de Wikipedia de que las macros recursivas son típicamente ilegales parece bastante poco informada. C y C++ evitar las invocaciones recursivas, pero una unidad de traducción no se vuelve ilegal al contener un código macro que parece que habría sido recursivo. Las macros ve son típicamente legales.

Answer 6

Consulte las respuestas ya dadas sobre por qué esto no suele funcionar.

Como "nota al pie", puede lograr el efecto que está buscando (al menos para el factorial que está utilizando como ejemplo) usando template metaprogramming. Pegar de Wikipedia:

template <int N> 
struct Factorial 
{ 
    enum { value = N * Factorial<N - 1>::value }; 
}; 

template <> 
struct Factorial<0> 
{ 
    enum { value = 1 }; 
}; 

Answer 7

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

Answer 8

Algunas funciones recursivas se pueden transformar en bucles, lo que las alinea infinitamente de forma efectiva. Creo que gcc puede hacer esto, pero no sé sobre otros compiladores.

Answer 9

Algunos compiladores (es decir, Borland C++) no incluyen el código en línea que contiene sentencias condicionales (por ejemplo, caso, etc.) por lo que la función recursiva en su ejemplo no estaría en línea.