Pelaksanaan rekursif fungsi C++: Adakah terdapat had untuk kedalaman rekursif?

Kedalaman rekursi fungsi C++ adalah terhad, melebihi had ini akan mengakibatkan ralat limpahan tindanan. Nilai had berbeza antara sistem dan penyusun, tetapi biasanya antara 1000 dan 10000. Penyelesaian termasuk: 1. Pengoptimuman rekursi ekor; 2. Panggilan ekor;

Pelaksanaan rekursif fungsi C++: Adakah terdapat had untuk kedalaman rekursi?

Dalam C++, rekursi ialah teknik berkuasa yang membolehkan fungsi memanggil diri mereka sendiri. Walau bagaimanapun, terdapat had untuk kedalaman rekursi, dan melebihi had ini menyebabkan ralat dipanggil limpahan tindanan.

Limpahan Tindanan

Setiap panggilan fungsi menolak beberapa data (seperti parameter fungsi, pembolehubah setempat dan alamat pemulangan) ke dalam tindanan. Apabila fungsi kembali, data ini akan muncul dari timbunan. Jika kedalaman rekursi terlalu besar, tindanan mungkin kehabisan, menyebabkan ralat limpahan tindanan.

Had kedalaman rekursi

C++ tidak mentakrifkan nilai khusus untuk had kedalaman rekursi kerana ia bergantung pada sistem dan pengkompil. Walau bagaimanapun, had biasanya boleh dianggap antara 1000 dan 10000.

Contoh Praktikal

Pertimbangkan fungsi rekursif berikut untuk mengira sebutan ke-n bagi jujukan Fibonacci:

int fib(int n) {
  if (n <= 1)
    return n;
  else
    return fib(n - 1) + fib(n - 2);
}

Jika anda cuba mengira fib(10000), ia akan menyebabkan limpahan tindanan kerana kedalaman rekursi melebihi had.

Penyelesaian

Terdapat beberapa penyelesaian untuk menyelesaikan masalah had kedalaman rekursi:

• Pengoptimuman Rekursi Ekor: Sesetengah penyusun boleh mengoptimumkan, dengan menukarnya keperluan rekursif ekor ke dalam keperluan rekursif ekor, mengubahnya secara berterusan .
• Panggilan ekor: Tukar panggilan rekursif secara manual kepada panggilan ekor, dan tetapkan parameter dan nilai pulangan kepada fungsi sebelum kembali.
• Pelaksanaan berulang: Tulis semula fungsi untuk menggunakan gelung dan bukannya rekursi untuk mengira hasilnya.

Kesimpulan

Kedalaman rekursi fungsi C++ adalah terhad. Had ini boleh diatasi melalui pengoptimuman rekursif ekor, panggilan ekor atau pelaksanaan berulang.

Atas ialah kandungan terperinci Pelaksanaan rekursif fungsi C++: Adakah terdapat had untuk kedalaman rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!