c++ - recursivos - recursividad en c pdf

¿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);
}

Mientras estaba leyendo this , descubrí que el código anterior llevaría a la "compilación infinita" si el compilador no lo maneja correctamente.

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

Answer 1

"¿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.

El código fuente del programa todavía tiene que obedecer las reglas para funciones en línea. Independientemente de 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 mal informada. C y C ++ evitan las invocaciones recursivas, pero una unidad de traducción no se vuelve ilegal al contener código macro que parece que hubiera sido recursivo. En ensambladores, las macros recursivas son generalmente legales.

Answer 2

AFAIK GCC hará la eliminación de llamadas de cola en funciones recursivas, si es posible. Sin embargo, su función no es recursiva de cola.

Answer 3

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

Answer 4

Algunos compiladores (es decir, Borland C ++) no incluyen 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.

Answer 5

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

1. No está en línea la función en absoluto
2. Inlinea hasta una cierta profundidad, y si no ha terminado para entonces, llame a la instancia separada de su función usando la convención de llamada de función estándar. 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 que puede establecer para especificar la profundidad máxima a la que esto debe hacerse. En gcc , también puede pasar esto desde la línea de comando con --max-inline-insns-recursive (ver más información here ).

Answer 6

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 7

El compilador creará un gráfico de llamadas para detectar este tipo de cosas y prevenirlas. 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 pila no se conservará para reflejar las llamadas que creó en el código.

Answer 8

En primer lugar, la especificación en inline de una función es solo una pista. El compilador puede (y muchas veces lo hace) ignorar por completo la presencia o ausencia de un calificador en inline . Dicho esto, un compilador puede alinear una función recursiva, del mismo modo que puede desenrollar un ciclo 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, básicamente hemos definido la función 3 veces. Algunos compiladores realizan 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 9

Vea las respuestas ya dadas sobre por qué esto normalmente no funcionará.

Como "nota al pie", puede lograr el efecto que está buscando (al menos para el factorial que está utilizando como ejemplo) utilizando la metaprogramación de plantillas . Pegando de Wikipedia:

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