Perkongsian pengalaman praktikal rekursi C++: ringkasan pengoptimuman dan kemahiran kod

Kemahiran pengoptimuman rekursif: Pengoptimuman rekursif ekor: Pengkompil melakukan semua pengiraan sebelum memanggil fungsi itu sendiri untuk meningkatkan kecekapan. Memori: Menyimpan output yang dikira sebelum ini untuk mengelakkan pengiraan berulang. Lelaran: Gunakan algoritma lelaran dan bukannya pengulangan untuk meningkatkan kebolehbacaan dan mengelakkan limpahan tindanan.

C++ rekursi perkongsian pengalaman praktikal: ringkasan pengoptimuman kod dan kemahiran

Dalam pembangunan sebenar, rekursi sering digunakan untuk menyelesaikan masalah yang kompleks. Ia membenarkan fungsi untuk memanggil diri mereka sendiri, mencipta tindanan panggilan bersarang. Walau bagaimanapun, panggilan rekursif yang berlebihan boleh menyebabkan limpahan tindanan dan ranap program.

Berikut ialah beberapa petua untuk mengoptimumkan kod rekursif, dengan kes praktikal:

1 Pengoptimuman rekursif ekor

Rekursif ekor merujuk kepada semua pengiraan yang dilakukan oleh fungsi sebelum memanggil dirinya sendiri, dan memanggil dirinya sendiri ialah tindakan terakhir bagi fungsi . Untuk panggilan rekursif ekor, pengkompil boleh mengoptimumkannya dengan menggantikan penuding fungsi dalam tindanan panggilan dan bukannya menolak bingkai tindanan baharu.

int factorial(int n) {
  return n == 0 ? 1 : n * factorial(n - 1);
}

Dengan menggunakan bendera pengoptimuman panggilan ekor, pengkompil boleh mengenali rekursi ini sebagai rekursi ekor dan mengoptimumkannya.

int factorial(int n) __attribute__ ((tailcall));

2. Ingatan

Memori ialah teknik yang digunakan untuk menyimpan output input yang sama yang dibentangkan sebelum ini. Apabila rekursi terus mengulangi pengiraan yang sama, hafalan boleh meningkatkan prestasi dengan ketara.

int fib(int n) {
  static std::map<int, int> memo;
  if (memo.count(n) > 0) {
    return memo[n];
  }
  return memo[n] = n < 2 ? n : fib(n - 1) + fib(n - 2);
}

Kod ini menggunakan std::map4101e4c0559e7df80e541d0df514fd80 memo untuk menyimpan nombor Fibonacci yang dikira sebelum ini.

3. Lelaran

Dalam sesetengah kes, masalah rekursif boleh digantikan dengan algoritma berulang. Melakukannya mengelakkan risiko limpahan tindanan dan meningkatkan kebolehbacaan kod.

int factorial(int n) {
  int result = 1;
  while (n > 0) {
    result *= n--;
  }
  return result;
}

Kod ini mengira faktorial secara berulang dan bukannya menggunakan rekursi.

Kes Praktikal

Jujukan Fibonacci

Mengira nombor Fibonacci pada indeks tertentu boleh digunakan sebagai kes praktikal klasik rekursi. Pelaksanaan rekursif menggunakan memoisasi adalah seperti berikut:

int fib(int n) {
  static std::map<int, int> memo;
  if (memo.count(n) > 0) {
    return memo[n];
  }
  return memo[n] = n < 2 ? n : fib(n - 1) + fib(n - 2);
}

Menggunakan kod ini, kita boleh mengira nombor Fibonacci yang besar dengan cekap tanpa perlu risau tentang limpahan tindanan.

Atas ialah kandungan terperinci Perkongsian pengalaman praktikal rekursi C++: ringkasan pengoptimuman dan kemahiran kod. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!