Une fonction récursive peut-elle être intégrée?

Question

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

En lisant 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'inclure ou non une fonction?

Answer 1

Tout d'abord, l' 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 de qualification. Cela dit, un compilateur peut incorporer 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).

Answer 2

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 séparée 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).

Answer 3

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

Answer 4

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

Answer 5

Certaines fonctions récursives peuvent être transformées en boucles, ce qui les induit efficacement à l'infini. Je pense que gcc peut le faire, mais je ne connais pas d'autres compilateurs.