Kann eine rekursive Funktion inline sein?

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

Als ich las diese gefunden, dass der obige Code auf „unendlich Compilation“ führen würde , wenn sie nicht richtig vom Compiler behandelt.

Wie entscheidet der Compiler, ob eine Funktion inline ist oder nicht?

Erstens ist die inlineSpezifikation einer Funktion nur ein Hinweis. Der Compiler kann (und tut dies häufig) das Vorhandensein oder Fehlen eines inlineQualifikators vollständig ignorieren . Mit dieser sagte, ein Compiler kann eine rekursive Funktion inline, viel , wie es eine unendliche Schleife abrollen kann. Es muss lediglich eine Grenze für die Ebene festgelegt werden, bis zu der die Funktion "abgewickelt" wird.

Ein optimierender Compiler könnte diesen Code umdrehen:

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

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

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

In diesem Fall haben wir die Funktion grundsätzlich dreimal eingefügt. Einige Compiler tun diese Optimierung durchführen. Ich erinnere mich, dass MSVC ++ eine Einstellung zum Einstellen des Inlining-Niveaus hat, das für rekursive Funktionen ausgeführt wird (bis zu 20, glaube ich).

Wenn Ihr Compiler nicht intelligent handelt, versucht er möglicherweise, Kopien Ihrer inlined-Funktion rekursiv einzufügen, wodurch unendlich großer Code erstellt wird. Die meisten modernen Compiler werden dies jedoch erkennen. Sie können entweder:

1. Die Funktion überhaupt nicht inline
2. Inline bis zu einer bestimmten Tiefe, und wenn es bis dahin nicht beendet ist, rufen Sie die separate Instanz Ihrer Funktion unter Verwendung der Standard-Funktionsaufrufkonvention auf. Dies kann viele häufig auftretende Fälle auf leistungsstarke Weise lösen und gleichzeitig einen Fallback für den seltenen Fall mit einer großen Anruftiefe hinterlassen. Dies bedeutet auch, dass Sie sowohl Inline- als auch separate Versionen des Funktionscodes beibehalten.

Für Fall 2 haben viele Compiler #pragmas, die Sie festlegen können, um die maximale Tiefe anzugeben, bis zu der dies durchgeführt werden soll. In gcc können Sie dies auch über die Befehlszeile mit übergeben --max-inline-insns-recursive(weitere Informationen finden Sie hier ).

AFAIK GCC führt nach Möglichkeit eine Tail-Call-Eliminierung für rekursive Funktionen durch. Ihre Funktion ist jedoch nicht rekursiv.

Der Compiler erstellt ein Aufrufdiagramm. Wenn ein Zyklus erkannt wird, der sich selbst aufruft, wird die Funktion nach einer bestimmten Tiefe nicht mehr inline (n = 1, 10, 100, unabhängig davon, auf was der Compiler eingestellt ist).

Einige rekursive Funktionen können in Schleifen umgewandelt werden, wodurch sie effektiv unendlich inline werden. Ich glaube, dass gcc das kann, aber ich weiß nichts über andere Compiler.

In den bereits gegebenen Antworten erfahren Sie, warum dies normalerweise nicht funktioniert.

Als "Fußnote" können Sie mithilfe der Metaprogrammierung von Vorlagen den gewünschten Effekt erzielen (zumindest für die Fakultät, die Sie als Beispiel verwenden) . Einfügen aus Wikipedia:

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

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

Der Compiler erstellt ein Aufrufdiagramm, um diese Art von Dingen zu erkennen und zu verhindern. Es würde also sehen, dass die Funktion sich selbst aufruft und nicht inline.

Hauptsächlich wird es jedoch durch die Inline-Schlüsselwort- und Compiler-Schalter gesteuert (Sie können beispielsweise kleine Funktionen auch ohne das Schlüsselwort automatisch inline schalten lassen.) Es ist wichtig zu beachten, dass Debug-Kompilierungen niemals inline sein sollten, da der Callstack nicht für die Spiegelung beibehalten wird die Aufrufe, die Sie im Code erstellt haben.

"Wie entscheidet der Compiler, ob eine Funktion inline ist oder nicht?"

Dies hängt vom Compiler, den angegebenen Optionen, der Versionsnummer des Compilers, möglicherweise dem verfügbaren Speicher usw. ab.

Der Quellcode des Programms muss weiterhin den Regeln für Inline-Funktionen entsprechen. Unabhängig davon, ob die Funktion inline geschaltet wird oder nicht, müssen Sie sich auf die Möglichkeit vorbereiten, dass sie inline geschaltet wird (eine unbekannte Anzahl von Malen).

Die Wikipedia-Aussage, dass rekursive Makros normalerweise illegal sind, sieht eher schlecht informiert aus. C und C ++ verhindern rekursive Aufrufe, aber eine Übersetzungseinheit wird nicht illegal, indem sie Makrocode enthält, der aussieht, als wäre er rekursiv gewesen. In Assemblern sind rekursive Makros normalerweise zulässig.

Einige Compiler (z. B. Borland C ++) enthalten keinen Inline-Code, der bedingte Anweisungen enthält (if, case, while usw.), sodass die rekursive Funktion in Ihrem Beispiel nicht inline ist.