Bisakah fungsi rekursif sejajar?

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

Saat saya membaca ini , menemukan bahwa kode di atas akan mengarah pada "kompilasi tak terbatas" jika tidak ditangani oleh kompilator dengan benar.

Bagaimana kompilator memutuskan apakah akan menyebariskan suatu fungsi atau tidak?

Pertama, inlinespesifikasi suatu fungsi hanyalah petunjuk. Kompilator dapat (dan sering kali) mengabaikan sepenuhnya ada atau tidaknya sebuah inlinequalifier. Dengan demikian, kompilator dapat menyebariskan fungsi rekursif, seperti halnya ia dapat membuka gulungan loop tak terbatas. Ini hanya harus menempatkan batas pada tingkat yang akan "membuka" fungsi.

Kompilator yang mengoptimalkan mungkin mengubah kode ini:

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

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

ke dalam kode ini:

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

Dalam kasus ini, pada dasarnya kita telah membuat inline fungsinya 3 kali. Beberapa compiler melakukan melakukan optimasi ini. Saya ingat MSVC ++ memiliki pengaturan untuk menyetel tingkat sebaris yang akan dilakukan pada fungsi rekursif (hingga 20, saya percaya).

Memang, jika kompilator Anda tidak bertindak secara cerdas, ia mungkin mencoba menyisipkan salinan inlinefungsi d Anda secara rekursif, membuat kode yang sangat besar. Namun, sebagian besar kompiler modern akan mengenali ini. Mereka dapat:

1. Tidak sebaris fungsi sama sekali
2. Sebariskan hingga kedalaman tertentu, dan jika belum diakhiri pada saat itu, panggil instance terpisah dari fungsi Anda menggunakan konvensi pemanggilan fungsi standar. Ini dapat menangani banyak kasus umum dengan performa tinggi, sementara meninggalkan fallback untuk kasus yang jarang terjadi dengan kedalaman panggilan yang besar. Ini juga berarti bahwa Anda tetap menggunakan versi kode fungsi yang sebaris dan terpisah.

Untuk kasus 2, banyak compiler yang #pragmadapat Anda atur untuk menentukan kedalaman maksimum yang harus dilakukan. Di gcc , Anda juga dapat meneruskan ini dari baris perintah dengan --max-inline-insns-recursive(lihat info selengkapnya di sini ).

AFAIK GCC akan melakukan tail call elimination pada fungsi rekursif, jika memungkinkan. Namun fungsi Anda tidak rekursif ekor.

Kompilator membuat grafik panggilan; ketika sebuah siklus terdeteksi memanggil dirinya sendiri, fungsinya tidak lagi sebaris setelah kedalaman tertentu (n = 1, 10, 100, apa pun kompilernya disetel).

Lihat jawaban yang sudah diberikan mengapa ini biasanya tidak berhasil.

Sebagai "catatan kaki", Anda bisa mendapatkan efek yang Anda cari (setidaknya untuk faktorial yang Anda gunakan sebagai contoh) menggunakan metaprogramming template . Menempel dari Wikipedia:

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

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

Beberapa fungsi rekursif dapat diubah menjadi loop, yang secara efektif membuat mereka menjadi sebaris tanpa batas. Saya yakin gcc bisa melakukan ini, tetapi saya tidak tahu tentang kompiler lain.

Kompilator akan membuat grafik panggilan untuk mendeteksi hal-hal semacam ini dan mencegahnya. Jadi akan terlihat bahwa fungsi memanggil dirinya sendiri dan bukan sebaris.

Tetapi sebagian besar dikendalikan oleh kata kunci inline dan switch kompilator (Misalnya, Anda dapat membuatnya menjadi fungsi kecil sebaris otomatis bahkan tanpa kata kunci.) Penting untuk dicatat bahwa kompilasi Debug tidak boleh sebaris karena callstack tidak akan disimpan ke mirror panggilan yang Anda buat dalam kode.

"Bagaimana kompilator memutuskan apakah akan menyebariskan suatu fungsi atau tidak?"

Itu tergantung pada kompilator, opsi yang ditentukan, nomor versi kompilator, mungkin berapa banyak memori yang tersedia, dll.

Kode sumber program tetap harus mematuhi aturan fungsi sebaris. Terlepas dari apakah fungsinya menjadi sebaris atau tidak, Anda harus bersiap untuk kemungkinan bahwa itu akan sebaris (beberapa kali tidak diketahui).

Pernyataan Wikipedia bahwa makro rekursif biasanya ilegal terlihat agak kurang informasi. C dan C ++ mencegah pemanggilan rekursif tetapi unit terjemahan tidak menjadi ilegal dengan berisi kode makro yang sepertinya rekursif. Di assembler, makro rekursif biasanya legal.

Beberapa kompiler (Ie Borland C ++) tidak memiliki kode inline yang berisi pernyataan kondisional (if, case, while dll ..) sehingga fungsi rekursif dalam contoh Anda tidak akan menjadi inline.