Bagaimana untuk menyelesaikan masalah limpahan timbunan fungsi rekursif C++?

Untuk masalah limpahan tindanan bagi fungsi rekursif C++, penyelesaiannya termasuk: mengurangkan kedalaman rekursi, mengurangkan saiz bingkai tindanan dan pengoptimuman rekursi ekor. Sebagai contoh, fungsi jujukan Fibonacci boleh mengelakkan limpahan tindanan melalui pengoptimuman rekursi ekor.

Bagaimana untuk menyelesaikan masalah limpahan tindanan fungsi rekursif dalam C++?

Sebab

Fungsi rekursif mencipta bingkai tindanan baharu pada tindanan setiap kali ia dipanggil. Apabila kedalaman rekursi terlalu besar dan ruang tindanan tidak mencukupi, limpahan tindanan akan berlaku.

Penyelesaian

1. Kurangkan kedalaman rekursi

• Cari algoritma bukan rekursif untuk menggantikan rekursi, seperti kaedah lelaran atau memo.
• Pisah panggilan rekursif dan kurangkan kedalaman rekursif.

2. Kurangkan saiz bingkai tindanan

• Gunakan pembolehubah tempatan dan bukannya pembolehubah ahli untuk mengurangkan saiz bingkai tindanan.
• Gunakan hantaran nilai dan bukannya hantaran rujukan untuk mengelakkan salinan berlebihan.

3. Pengoptimuman rekursif ekor

• Apabila panggilan terakhir bagi fungsi rekursif adalah rekursif ekor (iaitu, fungsi itu tidak melakukan sebarang operasi lain dan memanggil dirinya sendiri secara langsung), pengkompil boleh melakukan pengoptimuman rekursif ekor. Ini menghapuskan bingkai tindanan yang diperlukan untuk panggilan rekursif, dengan berkesan menyelesaikan masalah limpahan tindanan.

Contoh Praktikal

Pertimbangkan fungsi jujukan Fibonacci berikut:

// 尾递归版本
int fibonacci(int n) {
  return fibonacci_helper(n, 0, 1);
}

int fibonacci_helper(int n, int a, int b) {
  if (n == 0) return a;
  return fibonacci_helper(n-1, b, a+b);
}

Ini ialah versi rekursif ekor kerana panggilan fungsi terakhir berulang terus ke dalam dirinya sendiri. Pengkompil akan mengoptimumkannya untuk mengelakkan limpahan tindanan.

Berikut ialah versi rekursif bukan ekor:

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

Untuk versi rekursif bukan ekor ini, anda boleh menggunakan teknik pengoptimuman rekursif ekor untuk menukarnya menjadi versi rekursif ekor. Contohnya, menggunakan fungsi tambahan dan operasi swap:

int fibonacci(int n, int a = 0, int b = 1) {
  if (n == 0) return a;
  if (n == 1) return b;
  // 进行 swap 操作
  std::swap(a, b);
  return fibonacci(n-1, b, a+b);
}

Dengan menggunakan pengoptimuman rekursi ekor atau mengurangkan kedalaman rekursi, masalah limpahan tindanan fungsi rekursif dalam C++ boleh diselesaikan dengan berkesan.

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah limpahan timbunan fungsi rekursif C++?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!