Uma função recursiva pode estar embutida?

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

Enquanto eu lia isso , descobri que o código acima levaria à "compilação infinita" se não fosse manipulado pelo compilador corretamente.

Como o compilador decide se alinha uma função ou não?

Primeiro, a inlineespecificação de uma função é apenas uma dica. O compilador pode (e geralmente o faz) ignorar completamente a presença ou ausência de um inlinequalificador. Com isso dito, um compilador pode incorporar uma função recursiva, da mesma forma que pode desenrolar um loop infinito. Ele simplesmente precisa colocar um limite no nível em que "desenrolará" a função.

Um compilador de otimização pode transformar esse 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);
}

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

Nesse caso, basicamente alinhamos a função 3 vezes. Alguns compiladores fazer executar esta otimização. Lembro que o MSVC ++ tinha uma configuração para ajustar o nível de inlining que seria executado em funções recursivas (até 20, acredito).

De fato, se seu compilador não agir de maneira inteligente, ele poderá tentar inserir cópias de sua inlinefunção d recursivamente, criando um código infinitamente grande. A maioria dos compiladores modernos reconhecerá isso, no entanto. Eles podem:

1. Não inline a função
2. Alinhe até uma certa profundidade e, se ainda não tiver terminado, chame a instância separada de sua função usando a convenção de chamada de função padrão. Isso pode cuidar de muitos casos comuns de maneira de alto desempenho, deixando um substituto para o caso raro com uma grande profundidade de chamada. Isso também significa que você mantém versões inline e separada do código dessa função.

No caso 2, muitos compiladores têm #pragmas que você pode definir para especificar a profundidade máxima com a qual isso deve ser feito. No gcc , você também pode passar isso da linha de comando com --max-inline-insns-recursive(veja mais informações aqui ).

O AFAIK GCC fará a eliminação da chamada de cauda em funções recursivas, se possível. Sua função, no entanto, não é recursiva da cauda.

O compilador cria um gráfico de chamada; quando um ciclo é detectado chamando a si próprio, a função não é mais incorporada após uma certa profundidade (n = 1, 10, 100, seja qual for o sintonizador do compilador).

Algumas funções recursivas podem ser transformadas em loops, que efetivamente as alinham infinitamente. Acredito que o gcc pode fazer isso, mas não conheço outros compiladores.

Veja as respostas já dadas sobre por que isso normalmente não funciona.

Como uma "nota de rodapé", você pode obter o efeito que está procurando (pelo menos para o fatorial que está usando como exemplo) usando a metaprogramação de modelos . Colagem da Wikipedia:

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

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

O compilador fará um gráfico de chamada para detectar esses tipos de coisas e evitá-las. Portanto, veria que a função se chama e não está embutida.

Mas, principalmente, ele é controlado pelas palavras-chave inline e pelas opções do compilador (por exemplo, você pode fazer com que as pequenas funções sejam incorporadas automaticamente, mesmo sem a palavra-chave.) É importante observar que as compilações de depuração nunca devem ser incorporadas, pois o pilha de chamadas não será preservada para espelhar as chamadas que você criou no código.

"Como o compilador decide se alinha uma função ou não?"

Isso depende do compilador, das opções especificadas, do número da versão do compilador, talvez da quantidade de memória disponível etc.

O código fonte do programa ainda precisa obedecer às regras para funções embutidas. Quer a função fique ou não incorporada, você deve se preparar para a possibilidade de ser incorporada (um número desconhecido de vezes).

A declaração da Wikipedia de que macros recursivas são tipicamente ilegais parece pouco informada. C e C ++ impedem invocações recursivas, mas uma unidade de tradução não se torna ilegal por conter código de macro que parece ter sido recursivo. Em montadores, macros recursivas geralmente são legais.

Alguns compiladores (ie Borland C ++) não incorporam código que contém instruções condicionais (se, caso, enquanto etc.), portanto a função recursiva no seu exemplo não seria incorporada.