Ralat kompilasi C++: Rekursi yang terlalu dalam menyebabkan limpahan tindanan Bagaimana untuk menyelesaikannya?

C++ ialah bahasa pengaturcaraan yang digunakan secara meluas, dan tidak dapat dielakkan untuk menghadapi pelbagai ralat semasa penyusunan dan pelaksanaannya. Satu kesilapan biasa ialah mengulangi terlalu dalam dan menyebabkan limpahan timbunan.

Dalam rekursi, apabila terdapat terlalu banyak tahap rekursi, program akan menghadapi ralat limpahan tindanan Ini kerana fungsi rekursif memerlukan sejumlah ruang memori untuk menyimpan pembolehubah setempat dan panggilan fungsi semasa setiap ulangan. Setiap rekursi akan menolak pembolehubah tempatan dan panggilan fungsi ke dalam timbunan panggilan fungsi Saiz timbunan adalah terhad Apabila had ini melebihi, limpahan timbunan akan berlaku, menyebabkan program ranap.

Jadi, bagaimanakah kita harus menyelesaikan limpahan tindanan yang disebabkan oleh rekursi yang terlalu dalam? Berikut adalah beberapa penyelesaian.

1. Tulis semula rekursi ke dalam gelung

Intipati fungsi rekursif ialah gelung dengan penjejakan ke belakang, jadi tanpa menjejaskan logik program, kita boleh menulis semula fungsi rekursif ke dalam gelung. Ini boleh mengurangkan overhed yang disebabkan oleh rekursi, dengan itu mengurangkan risiko limpahan tindanan.

Sebagai contoh, berikut ialah fungsi rekursif yang mengira jujukan Fibonacci:

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Kita boleh menulis semula ke dalam bentuk gelung berikut:

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

2. Tingkatkan ruang tindanan

Kita boleh mengelakkannya dengan menetapkan saiz ini dengan menetapkan saiznya. ruang timbunan Limpahan timbunan. Di bawah Windows, ini boleh dicapai dengan mengubah suai saiz ruang tindanan bagi fail boleh laku program di bawah Linux, anda boleh menggunakan perintah ulimit untuk mengawal saiz tindanan. Satu perkara yang perlu diperhatikan dengan pendekatan ini ialah terlalu banyak ruang tindanan akan menduduki sumber sistem, jadi anda perlu menimbang kebaikan dan keburukan.

3. Laraskan algoritma rekursif

Kadangkala, algoritma rekursif itu sendiri mungkin menghadapi masalah, mengakibatkan terlalu banyak tahap rekursif. Dalam kes ini, kita perlu mengoptimumkan algoritma rekursif dan mengurangkan bilangan panggilan rekursif untuk mengurangkan risiko limpahan tindanan.

Sebagai contoh, berikut ialah algoritma rekursif untuk menyelesaikan jujukan Fibonacci:

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Kami boleh mengoptimumkan algoritma ini melalui carian dihafal untuk mengurangkan bilangan panggilan rekursif:

int fib(int n, unordered_map<int, int>& memo) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = ans;
    return ans;
}

int fib(int n) {
    unordered_map<int, int> memo;
    return fib(n, memo);
}

4. Elakkan pengiraan berulang bagi fungsi rekursif

fungsi rekursif, mungkin terdapat sub-masalah pengiraan berulang. Kita boleh mengelakkan ini menggunakan mekanisme caching untuk mengurangkan bilangan panggilan rekursif.

Sebagai contoh, jika kita perlu mengira nombor Catalan, kita boleh menggunakan mekanisme caching untuk mengelakkan pengiraan berulang:

int catalan(int n, unordered_map<int, int>& memo) {
    if (n <= 1) {
        return 1;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += catalan(i, memo) * catalan(n - 1 - i, memo);
    }
    memo[n] = ans;
    return ans;
}

int catalan(int n) {
    unordered_map<int, int> memo;
    return catalan(n, memo);
}

Ringkasnya, terdapat banyak cara untuk mengelakkan limpahan tindanan yang disebabkan oleh ulangan yang terlalu dalam, dan kita perlu memilih kaedah yang sesuai mengikut situasi tertentu. Semasa menulis fungsi rekursif, pastikan anda memberi perhatian kepada kedalaman rekursif dan uji sepenuhnya untuk memastikan program berjalan dengan betul.

Atas ialah kandungan terperinci Ralat kompilasi C++: Rekursi yang terlalu dalam menyebabkan limpahan tindanan Bagaimana untuk menyelesaikannya?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!