C Academy · Pelajaran

Mengelakkan Limpahan Tindanan

Pastikan rekursi mempunyai had.

Pelajaran 4 daripada 413 langkah

Mengelakkan Limpahan Tindanan ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Apakah Limpahan Tindanan?

Tindanan panggilan mempunyai saiz yang terhad. Setiap panggilan fungsi menggunakan sebahagian daripadanya untuk parameter dan pemboleh ubah setempat.

Jika rekursi menjadi terlalu dalam, tindanan akan penuh dan atur cara ranap dengan limpahan tindanan.

Kes Asas Tiada

Punca yang paling biasa ialah kes asas yang tidak pernah dicapai. Keadaan ini berulang tanpa henti dan menyebabkan tindanan melimpah.

Jangan jalankan fungsi seperti ini; kaji sebab kegagalannya.

int broken(int n) {
    /* no base case: never stops */
    return broken(n + 1);
}

Argumen Tidak Mengecil

Walaupun terdapat kes asas, argumen mesti bergerak menghampirinya. Di sini n meningkat, jadi ia tidak pernah mencapai 0.

Sentiasa semak bahawa setiap panggilan menjadi lebih hampir kepada syarat penghentian.

int oops(int n) {
    if (n == 0) return 0;
    return oops(n + 1); /* wrong direction */
}

Versi yang Betul

Membetulkan arahnya menjadikan fungsi itu berhenti. Kini n berkurang menuju kes asas 0.

#include <stdio.h>

int good(int n) {
    if (n == 0) return 0;
    return n + good(n - 1);
}

int main(void) {
    printf("%d\n", good(10));
    return 0;
}

Had Kedalaman Itu Nyata

Rekursi yang betul sekalipun boleh menyebabkan limpahan jika terlalu dalam. Memanggil fungsi sehingga berjuta-juta aras mungkin melebihi kapasiti tindanan, yang selalunya hanya beberapa megabait.

Untuk kedalaman yang sangat besar, utamakan lelaran.

Tukar Rekursi yang Dalam kepada Gelung

Jika kedalaman rekursi meningkat mengikut saiz input, tukarlah kepada gelung. Ini mengelakkan ribuan bingkai daripada disusun.

Gelung di bawah menjumlahkan 1 hingga n yang besar dengan selamat menggunakan memori malar.

#include <stdio.h>

int main(void) {
    long total = 0;
    for (int i = 1; i <= 1000000; i++)
        total += i;
    printf("%ld\n", total);
    return 0;
}

Kurangkan Kedalaman dengan Bahagi dan Takluk

Membahagikan kerja kepada dua mengekalkan kedalaman yang kecil. Menjumlahkan suatu julat dengan membahagikannya kepada dua menyebabkan kedalaman meningkat seperti log saiz, bukannya secara linear.

long range_sum(int lo, int hi) {
    if (lo == hi) return lo;
    int mid = (lo + hi) / 2;
    return range_sum(lo, mid) + range_sum(mid + 1, hi);
}

Berhati-hati dengan Tatasusunan Setempat yang Besar

Pemboleh ubah setempat yang besar menjadikan setiap bingkai berat, lalu tindanan menjadi penuh dengan lebih cepat.

Elakkan mengisytiharkan tatasusunan besar di dalam fungsi rekursif; hantarkan penuding atau gunakan heap sebagai ganti.

void heavy(int n) {
    int buffer[10000]; /* big frame each call */
    if (n == 0) return;
    heavy(n - 1);
}

Gunakan Pengumpul

Menghantar jumlah berjalan sebagai pengumpul mengekalkan saiz setiap bingkai agar kecil dan menjadikan bentuk rekursi itu seperti rekursi ekor.

Sesetengah pengkompil kemudiannya boleh menggunakan semula satu bingkai.

#include <stdio.h>

long sum_acc(int n, long acc) {
    if (n == 0) return acc;
    return sum_acc(n - 1, acc + n);
}

int main(void) {
    printf("%ld\n", sum_acc(100, 0));
    return 0;
}

Senarai Semak Keselamatan

Sebelum mempercayai fungsi rekursif, semak:

1. Adakah terdapat kes asas?
2. Adakah setiap panggilan bergerak menghampirinya?
3. Bolehkah kedalamannya menjadi sangat besar untuk input yang besar?

Jika kedalaman boleh meningkat secara mendadak, gunakan gelung sebagai ganti.

Menguji dengan Input Kecil

Sentiasa uji rekursi terlebih dahulu dengan input yang sangat kecil dan boleh disahkan secara manual.

Jika kes kecil berfungsi dan kedalamannya kekal terhad, anda boleh meningkatkan saiz input dengan yakin.

Semakan Pantas

Kenal pasti pembaikan yang paling selamat.

Jawab dalam pelajaran interaktif

Imbas Kembali

Limpahan tindanan berlaku apabila rekursi menjadi terlalu dalam atau tidak pernah berhenti. Sentiasa sediakan kes asas yang boleh dicapai, kecilkan argumen pada setiap panggilan, kekalkan bingkai agar ringan dan tukar kepada lelaran apabila kedalaman boleh meningkat mengikut saiz input.

Percuma untuk bermula

Pelajari C dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 39
Pelajaran: 144

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Mengelakkan Limpahan Tindanan” percuma?

Ya — teks penuh “Mengelakkan Limpahan Tindanan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Mengelakkan Limpahan Tindanan”?

Pastikan rekursi mempunyai had. Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan C Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “Mengelakkan Limpahan Tindanan” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke C Academy