Menukar Gelung kepada Rekursi: Templat dan Rekursi Ekor Diterangkan

Rekursi dan gelung ialah kedua-dua alat asas untuk melaksanakan tugas berulang dalam pengaturcaraan. Walaupun gelung suka untuk dan sementara adalah intuitif untuk kebanyakan pembangun, rekursi menawarkan pendekatan yang lebih abstrak dan fleksibel untuk menyelesaikan masalah. Artikel ini meneroka cara menukar gelung kepada fungsi rekursif, menyediakan templat umum dan menerangkan konsep dan pengoptimuman pengulangan ekor.

---

Memahami Rekursi

Apakah Rekursi?

Rekursi ialah teknik di mana fungsi memanggil dirinya sendiri untuk menyelesaikan kejadian yang lebih kecil daripada masalah yang sama. Tingkah laku rujukan kendiri ini berterusan sehingga syarat asas yang ditentukan dipenuhi.

Contohnya, mengira pemfaktoran nombor menggunakan rekursi:

function factorial(n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

Dalam contoh ini, faktorial(n - 1) mengurangkan saiz masalah dengan setiap panggilan, akhirnya ditamatkan apabila n ialah 1.

---

Menukar Gelung kepada Rekursi

Templat Umum untuk Menggantikan Gelung

Untuk menukar gelung kepada rekursi, ikut langkah berikut:

1. Kenal pasti Keadaan Lelaran: Tentukan pembolehubah yang berubah semasa setiap lelaran gelung (cth., pembilang atau indeks).
2. Tentukan Kes Asas: Tentukan bila rekursi harus berhenti, sama dengan keadaan keluar gelung.
3. Lakukan Kerja Lelaran Semasa: Laksanakan logik lelaran gelung semasa.
4. Panggilan Rekursif: Maju ke arah huruf besar dengan mengemas kini keadaan lelaran.

templat

function recursiveFunction(iterationState, dataOrAccumulator) {
  // Base case: Define when recursion stops
  if (baseCondition(iterationState)) {
    return dataOrAccumulator; // Final result
  }

  // Perform the action for the current iteration
  const updatedData = updateAccumulator(dataOrAccumulator, iterationState);

  // Recursive call with updated state
  return recursiveFunction(updateIterationState(iterationState), updatedData);
}

Contoh

Contoh 1: Menjumlahkan Array

Menggunakan Gelung:

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

Menggunakan Rekursi:

function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0; // Base case
  return arr[index] + sumArrayRecursive(arr, index + 1); // Recursive case
}

Contoh 2: Pemasa Undur

Menggunakan Gelung:

function countdown(n) {
  while (n > 0) {
    console.log(n);
    n--;
  }
}

Menggunakan Rekursi:

function countdownRecursive(n) {
  if (n <= 0) return; // Base case
  console.log(n); // Current iteration work
  countdownRecursive(n - 1); // Recursive case
}

---

Memahami Rekursi Ekor

Apakah Rekursi Ekor?

Ekor rekursi ialah bentuk khas rekursi di mana panggilan rekursif adalah operasi terakhir dalam fungsi. Ini bermakna tiada pengiraan tambahan berlaku selepas panggilan rekursif kembali.

Contoh Rekursi Ekor:

function factorialTailRecursive(n, accumulator = 1) {
  if (n <= 1) return accumulator; // Base case
  return factorialTailRecursive(n - 1, accumulator * n); // Tail-recursive call
}

Contoh Rekursi Bukan Ekor:

function factorial(n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

Faedah Rekursi Ekor

1. Pengoptimuman Tindanan: Fungsi rekursif ekor boleh dioptimumkan dengan menggunakan semula bingkai tindanan semasa dan bukannya mencipta yang baharu untuk setiap panggilan. Ini mengurangkan penggunaan memori dan menghalang limpahan tindanan.
2. Kecekapan: Rekursi ekor boleh menyamai prestasi gelung lelaran apabila pengoptimuman panggilan ekor (TCO) disokong oleh enjin JavaScript.

---

Templat untuk Rekursi Ekor

Untuk menulis fungsi rekursif ekor, ikut corak ini:

1. Utamakan Keadaan Lelaran: Keadaan lelaran (cth., pembilang, indeks) hendaklah menjadi hujah pertama.
2. Gunakan Akumulator: Gunakan parameter tambahan untuk membawa hasil perantaraan.
3. Panggilan Rekursif sebagai Operasi Terakhir: Pastikan panggilan rekursif ialah tindakan terakhir dalam fungsi.

Templat Ekor-Rekursif

function recursiveFunction(iterationState, dataOrAccumulator) {
  // Base case: Define when recursion stops
  if (baseCondition(iterationState)) {
    return dataOrAccumulator; // Final result
  }

  // Perform the action for the current iteration
  const updatedData = updateAccumulator(dataOrAccumulator, iterationState);

  // Recursive call with updated state
  return recursiveFunction(updateIterationState(iterationState), updatedData);
}

---

Contoh Rekursi Ekor

Contoh 1: Penjumlahan Ekor-Rekursif Suatu Tatasusunan

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

Contoh 2: Faktorial-Rekursif Ekor

function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0; // Base case
  return arr[index] + sumArrayRecursive(arr, index + 1); // Recursive case
}

---

Kelebihan dan Had Rekursi

Kelebihan

1. Keterekspresian: Rekursi lebih intuitif untuk masalah yang melibatkan struktur hierarki atau bahagi-dan-takluk, seperti lintasan pokok dan carian graf.
2. Kod Pembersih: Penyelesaian rekursif boleh menghapuskan kod boilerplate, terutamanya untuk masalah yang rumit.
3. Pendekatan Generik: Rekursi boleh menggantikan gelung dan menyelesaikan masalah seperti menjejak ke belakang, yang menyusahkan dengan gelung.

Had

1. Limpahan Tindanan: Fungsi rekursif yang bukan rekursif ekor atau melibatkan rekursif dalam boleh melebihi had tindanan panggilan.
2. Overhed Prestasi: Setiap panggilan rekursif menambah pada tindanan, menjadikan rekursi naif kurang cekap berbanding gelung.
3. Sokongan Penyemak Imbas Terhad untuk TCO: Tidak semua enjin JavaScript menyokong pengoptimuman panggilan ekor, mengehadkan penggunaan praktikal rekursi ekor dalam persekitaran tertentu.

---

Kesimpulan

Menukar gelung kepada rekursi ialah teknik berkuasa yang membolehkan kod yang lebih abstrak dan fleksibel. Dengan memahami dan menggunakan templat rekursif, pembangun boleh menggantikan binaan berulang dengan penyelesaian rekursif. Memanfaatkan rekursi ekor seterusnya meningkatkan prestasi dan mengurangkan risiko limpahan tindanan, dengan syarat persekitaran menyokong pengoptimuman panggilan ekor.

Menguasai konsep ini membuka pintu untuk menyelesaikan pelbagai masalah yang lebih luas dengan cekap dan elegan.

Atas ialah kandungan terperinci Menukar Gelung kepada Rekursi: Templat dan Rekursi Ekor Diterangkan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!