Czy funkcja rekurencyjna może być wbudowana?

134
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?

Ashwin
źródło

Odpowiedzi:

137

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ę).

Derek Park
źródło
20
to jest #pragma inline_recursion (on). Dokumentacja dotycząca maksymalnej głębokości nie jest spójna lub niejednoznaczna. Możliwe są wartości 8, 16 lub wartość #pragma inline_depth.
peterchen
@peterchen Jeśli funkcja wbudowana zmienia wartość jednego ze swoich argumentów, co się dzieje, myślę, że lepiej jest wstawić funkcję wewnątrz faktów zamiast w main. Przepraszam za mój angielski
ob_dev
1
@obounaim: Możesz tak pomyśleć. MSVC nie.
SecurityMatt
23

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 ).

Matt J
źródło
7

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

leppie
źródło
6

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).

Paul Nathan
źródło
3

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.

Alex dziwne
źródło
2

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 };
};
yungchin
źródło
1
To bardzo fajne, ale proszę zauważyć, że oryginalna wiadomość miała zmienny argument „int n”.
Programista Windows
1
To prawda, ale nie ma też sensu chcieć "rekursywnego wstawiania", gdy n nie jest znane w czasie kompilacji ... jak kompilator mógłby kiedykolwiek to osiągnąć? Więc w kontekście pytania myślę, że jest to odpowiednia alternatywa.
yungchin
1
Zobacz przykład Dereka Parka, jak to zrobić: Dwukrotne wstawianie powoduje powtórzenie n >> 2 razy i otrzymujesz 2 + 2 zwroty z wynikowego kodu.
MSalters
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.

mattlant
źródło
1

„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.

Programista Windows
źródło
0

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.

Roger Nelson
źródło