Peut une fonction récursive être en ligne?

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

Que je lisais cette, a constaté que le code ci-dessus conduirait à "l'infini de la compilation" si ce n'est pas manipulé par le compilateur correctement.

Comment le compilateur décider d'incorporer une fonction ou pas ?

InformationsquelleAutor Ashwin | 2008-10-10
  1. 134

    Tout d'abord, le inline sur une spécification de la fonction est juste un soupçon. Le compilateur peut (souvent) d'ignorer complètement la présence ou l'absence d'un inline qualificatif. Cela dit, un compilateur peut inline une fonction récursive, autant qu'il peut dérouler une boucle infinie. Il suffit de placer une limite sur le niveau de "dérouler" la fonction.

    Un compilateur optimisant pourrait tourner 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 essentiellement inline à la fonction 3 fois. Certains compilateurs ne effectuer cette optimisation. Je me souviens de MSVC++ d'avoir un réglage pour ajuster le niveau de l'in-lining, qui seront réalisés sur les fonctions récursives (jusqu'à 20, je crois).

    • il est #pragma inline_recursion(sur). De la Documentation sur la profondeur maximale n'est pas conforme ou ne sont pas concluants. Les valeurs 8, 16, ou de la valeur de #pragma inline_depth sont possibles.
    • Si la fonction inline est en train de changer la valeur de l'un de ses arguments de ce qui se passe, je pense que c'est mieux de l'inclure la fonction à l'intérieur de fait au lieu de principal. Désolé pour mon anglais
    • Vous pourriez penser que. MSVC ne l'est pas.
    InformationsquelleAutor Derek Park
  2. 23

    En effet, si votre compilateur ne pas agir intelligemment, il peut essayer d'insérer des copies de vos inlined fonction de manière récursive, en créant à l'infini-grand code. Plus les compilateurs modernes reconnaît cela, cependant. Ils peuvent soit:

    1. Pas inline de la fonction à tous les
    2. Inline jusqu'à une certaine profondeur, et si elle n'a pas terminé d'ici là, l'appel de l'instance distincte de votre fonction à l'aide de la fonction standard de convention d'appel. Cela peut prendre soin d'un grand nombre de cas dans une haute performance, tout en laissant une solution de repli pour le cas rare avec une grande profondeur d'appel. Cela signifie également que vous garder à la fois intégrées et des versions distinctes de ce code de fonction autour de.

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

    InformationsquelleAutor Matt J
  3. 7

    Autant que je sache, GCC fera appel tail élimination sur les fonctions récursives, si possible. Votre fonction n'est cependant pas la queue récursive.

    InformationsquelleAutor leppie
  4. 6

    Le compilateur crée un graphe d'appel; lorsqu'un cycle est détecté appelant elle-même, la fonction n'est plus inline après une certaine profondeur(n=1, 10, 100, quel que soit le compilateur est à l'écoute pour).

    InformationsquelleAutor Paul Nathan
  5. 3

    Certaines fonctions récursives peuvent être transformés en boucles, qui a effectivement infiniment inlines eux. Je crois que gcc peut le faire, mais je ne sais pas pour les autres compilateurs.

    InformationsquelleAutor alex strange
  6. 2

    Voir les réponses déjà pourquoi ce ne présentent généralement pas de travail.

    Comme une "note de bas de page", vous pouvez obtenir l'effet que vous recherchez (au moins pour la factorielle vous êtes en utilisant, comme un exemple) à l'aide de modèle de métaprogrammation. Coller de Wikipedia:

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

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};
    • C'est très mignon, mais s'il vous plaît notez que le message d'origine a un argument variable "int n".
    • Vrai, mais il y a aussi peu de sens à vouloir "récursive inline" lorsque n n'est pas connu au moment de la compilation... comment le compilateur jamais y parvenir? Dans le contexte de la question, je pense que c'est une alternative pertinente.
    • Voir Derek Parc de l'exemple, comment le faire: Par l'in-lining deux fois, vous recurse n>>2 fois et vous avez 2+2 retours à partir du code résultant.
    InformationsquelleAutor yungchin
  7. 1

    Le compilateur va faire un graphe d'appel pour détecter ces sortes de choses et de les prévenir. Il serait ainsi voir que la fonction s'appelle elle-même et non pas sur la ligne.

    Mais surtout il est contrôlé par le mot-clé inline et des commutateurs du compilateur(Par exemple, vous pouvez faire l'auto inline petites fonctions, même sans le mot clé.) Il est important de noter que le Débogage des compilations ne doit jamais être inline comme la pile des appels ne seront pas conservées pour refléter les appels que vous avez créé dans le code.

    InformationsquelleAutor mattlant
  8. 1

    "Comment le compilateur décider d'incorporer une fonction ou pas ?"

    Qui dépend du compilateur, les options qui ont été spécifiées, le numéro de version du compilateur, peut-être la quantité de mémoire disponible, etc.

    Le code source du programme a toujours obéir aux règles pour les fonctions inline. Si oui ou non la fonction est insérée, vous avez à vous préparer pour la possibilité qu'il soit incorporé (un inconnu nombre de fois).

    Le Wikipedia déclaration que récursive macros sont généralement illégal semble plutôt mal informé. Le C et le C++ empêcher récursive des invocations, mais une unité de traduction n'est pas devenue illégale en ce qu'elle contient le code de macro qui ressemble comme il aurait été récursive. Dans des monteurs, des macros récursives sont généralement juridique.

    InformationsquelleAutor Windows programmer
  9. 0

    Certains compilateurs (I. e. Borland C++) n'ont pas de code en ligne qui contient les instructions conditionnelles (si, cas, tout etc..) donc la fonction récursive dans votre exemple ne serait pas insérée.

    InformationsquelleAutor Roger Nelson