Une fonction récursive peut-elle être en ligne?

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

Pendant que je lisais ceci , j'ai trouvé que le code ci-dessus conduirait à une "compilation infinie" s'il n'était pas géré correctement par le compilateur.

Comment le compilateur décide-t-il d'insérer une fonction ou non?

Premièrement, la inlinespécification d'une fonction n'est qu'un indice. Le compilateur peut (et le fait souvent) ignorer complètement la présence ou l'absence d'un inlinequalificatif. Cela dit, un compilateur peut insérer une fonction récursive, tout comme il peut dérouler une boucle infinie. Il doit simplement placer une limite sur le niveau auquel il "déroulera" la fonction.

Un compilateur d'optimisation peut transformer ce code:

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

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

dans ce code:

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

Dans ce cas, nous avons fondamentalement intégré la fonction 3 fois. Certains compilateurs font effectuer cette optimisation. Je me souviens que MSVC ++ avait un paramètre pour régler le niveau d'inlining qui serait effectué sur les fonctions récursives (jusqu'à 20, je crois).

En effet, si votre compilateur n'agit pas intelligemment, il peut essayer d'insérer des copies de votre inlinefonction d de manière récursive, créant du code infiniment grand. La plupart des compilateurs modernes le reconnaîtront cependant. Ils peuvent soit:

1. Pas du tout en ligne la fonction
2. Inlinez-le jusqu'à une certaine profondeur, et s'il ne s'est pas terminé d'ici là, appelez l'instance distincte de votre fonction en utilisant la convention d'appel de fonction standard. Cela peut prendre en charge de nombreux cas courants de manière haute performance, tout en laissant une solution de secours pour le cas rare avec une grande profondeur d'appel. Cela signifie également que vous conservez les versions intégrées et séparées du code de cette fonction.

Pour le cas 2, de nombreux compilateurs ont des #pragmas que vous pouvez définir pour spécifier la profondeur maximale à laquelle cela doit être fait. Dans gcc , vous pouvez également le transmettre à partir de la ligne de commande avec --max-inline-insns-recursive(voir plus d'informations ici ).

AFAIK GCC fera si possible l'élimination des appels de queue sur les fonctions récursives. Votre fonction n'est cependant pas récursive en queue.

Le compilateur crée un graphe d'appel; lorsqu'un cycle est détecté en s'appelant, la fonction n'est plus en ligne après une certaine profondeur (n = 1, 10, 100, quel que soit le réglage du compilateur).

Certaines fonctions récursives peuvent être transformées en boucles, qui les insèrent effectivement à l'infini. Je crois que gcc peut le faire, mais je ne connais pas les autres compilateurs.

Voir les réponses déjà données pour savoir pourquoi cela ne fonctionne généralement pas.

En tant que "note de bas de page", vous pouvez obtenir l'effet que vous recherchez (au moins pour la factorielle que vous utilisez comme exemple) en utilisant une métaprogrammation de modèle . Collage depuis Wikipedia:

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

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

Le compilateur créera un graphe d'appel pour détecter ce genre de choses et les empêcher. Ainsi, il verrait que la fonction s'appelle elle-même et non en ligne.

Mais principalement, il est contrôlé par le mot-clé en ligne et les commutateurs du compilateur (par exemple, vous pouvez l'avoir automatiquement en ligne de petites fonctions même sans le mot-clé.) Il est important de noter que les compilations de débogage ne doivent jamais être intégrées car la pile d'appels ne sera pas conservée pour refléter les appels que vous avez créés dans le code.

"Comment le compilateur décide-t-il s'il doit incorporer une fonction ou non?"

Cela dépend du compilateur, des options spécifiées, du numéro de version du compilateur, peut-être de la quantité de mémoire disponible, etc.

Le code source du programme doit toujours obéir aux règles des fonctions intégrées. Que la fonction soit intégrée ou non, vous devez vous préparer à la possibilité qu'elle soit intégrée (un nombre inconnu de fois).

La déclaration de Wikipedia selon laquelle les macros récursives sont généralement illégales semble plutôt mal informée. C et C ++ empêchent les invocations récursives mais une unité de traduction ne devient pas illégale en contenant du code de macro qui semble avoir été récursif. Dans les assembleurs, les macros récursives sont généralement légales.

Certains compilateurs (Ie Borland C ++) n'intègrent pas de code contenant des instructions conditionnelles (if, case, while etc.) donc la fonction récursive de votre exemple ne serait pas insérée.