Czy funkcja rekurencyjna może być wbudowana?

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

Jak czytałem to , okazało się, że powyższy kod doprowadziłoby do „nieskończonej kompilacji”, jeśli nie obsługiwane przez kompilator poprawnie.

W jaki sposób kompilator decyduje, czy wstawić funkcję, czy nie?

Po pierwsze, inlinespecyfikacja funkcji jest tylko wskazówką. Kompilator może (i często to robi) całkowicie ignorować obecność lub brak inlinekwalifikatora. Mając to na uwadze, kompilator może wbudować funkcję rekurencyjną, podobnie jak może rozwinąć nieskończoną pętlę. Musi po prostu nałożyć ograniczenie na poziom, do którego „rozwinie” funkcję.

Kompilator optymalizujący może zmienić ten kod:

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

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

do tego kodu:

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

W tym przypadku w zasadzie wstawiliśmy funkcję 3 razy. Niektóre kompilatory zrobić wykonać tę optymalizację. Przypominam sobie, że MSVC ++ miało ustawienie do dostrojenia poziomu inliningu, który byłby wykonywany na funkcjach rekurencyjnych (do 20, jak sądzę).

Rzeczywiście, jeśli twój kompilator nie działa inteligentnie, może spróbować wstawić kopie inlinefunkcji d rekurencyjnie, tworząc nieskończenie duży kod. Jednak większość współczesnych kompilatorów to rozpozna. Mogą:

1. W ogóle nie jest wbudowana w funkcję
2. Wstaw ją do określonej głębokości i jeśli nie zakończyła się do tego czasu, wywołaj oddzielne wystąpienie funkcji, używając standardowej konwencji wywoływania funkcji. Może to załatwić wiele typowych przypadków w sposób o wysokiej wydajności, pozostawiając rezerwę dla rzadkich przypadków o dużej głębokości wywołania. Oznacza to również, że przechowujesz zarówno wbudowane, jak i oddzielne wersje kodu tej funkcji.

W przypadku 2 wiele kompilatorów ma #pragmas, które możesz ustawić, aby określić maksymalną głębokość, na jaką należy to zrobić. W gcc możesz również przekazać to z wiersza poleceń za pomocą --max-inline-insns-recursive(zobacz więcej informacji tutaj ).

AFAIK GCC wykona eliminację wywołań końcowych w funkcjach rekurencyjnych, jeśli to możliwe. Twoja funkcja nie jest jednak rekurencyjna.

Kompilator tworzy wykres wywołań; gdy wykryty zostanie cykl wywołujący sam siebie, funkcja nie jest już wstawiana po określonej głębokości (n = 1, 10, 100, niezależnie od dostrojenia kompilatora).

Niektóre funkcje rekurencyjne można przekształcić w pętle, które skutecznie je wprowadzają w nieskończoność. Wierzę, że gcc może to zrobić, ale nie znam innych kompilatorów.

Zobacz odpowiedzi już udzielone, aby dowiedzieć się, dlaczego to zwykle nie działa.

Jako „przypis” możesz osiągnąć efekt, którego szukasz (przynajmniej dla silni, której używasz jako przykładu) przy użyciu metaprogramowania szablonowego . Wklejanie z Wikipedii:

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

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

Kompilator utworzy wykres wywołań, aby wykryć tego rodzaju rzeczy i im zapobiec. Więc zobaczyłoby, że funkcja wywołuje samą siebie, a nie wbudowaną.

Ale głównie jest kontrolowany przez słowo kluczowe inline i przełączniki kompilatora (na przykład możesz ustawić automatyczne inline małe funkcje nawet bez słowa kluczowego). Ważne jest, aby pamiętać, że kompilacje debugowania nigdy nie powinny być wbudowane, ponieważ stos wywołań nie zostanie zachowany wywołania utworzone w kodzie.

„W jaki sposób kompilator decyduje, czy wstawić funkcję, czy nie?”

To zależy od kompilatora, określonych opcji, numeru wersji kompilatora, być może ilości dostępnej pamięci itp.

Kod źródłowy programu nadal musi być zgodny z regułami funkcji wbudowanych. Niezależnie od tego, czy funkcja zostanie wstawiona, czy nie, musisz przygotować się na możliwość, że zostanie ona wstawiona (nieznana liczba razy).

Stwierdzenie Wikipedii, że makra rekurencyjne są zazwyczaj nielegalne, wygląda raczej na słabo poinformowane. C i C ++ zapobiegają wywołaniom rekurencyjnym, ale jednostka translacyjna nie staje się nielegalna, ponieważ zawiera kod makra, który wygląda tak, jakby był rekurencyjny. W asemblerach makra rekurencyjne są zwykle dozwolone.

Niektóre kompilatory (np. Borland C ++) nie zawierają wbudowanego kodu zawierającego instrukcje warunkowe (if, case, while itd.), Więc funkcja rekurencyjna w naszym przykładzie nie byłaby wstawiana.