PHP - Fungsi Rekursif

Hai sana, para pemrogram yang sedang mencari ilmu! Hari ini, kita akan memantulkan dunia yang menarik dari fungsi rekursif dalam PHP. Jangan khawatir jika Anda baru saja memulai dalam pemrograman; saya akan mengarahkan Anda melalui konsep ini secara langkah demi langkah, sama seperti yang saya lakukan bagi ribuan murid saya selama tahun-tahun mengajar. Jadi, ambil secangkir kopi (atau minuman favorit Anda), dan mari kita memulai perjalanan yang menarik ini bersama!

PHP - Recursive Functions

Apa Itu Fungsi Rekursif?

Sebelum kita masuk ke hal-hal yang rumit, mari kita memahami apa itu fungsi rekursif. Bayangkan Anda melihat diri Anda sendiri di dalam cermin, dan di belakang Anda ada cermin lain. Anda akan melihat refleksi tak terbatas dari diri Anda sendiri, kan? Itu agak mirip dengan cara kerja fungsi rekursif dalam pemrograman!

Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri saat eksekusi. Itu seperti versi digital boneka Rusia yang bersarang, di mana setiap boneka berisi versi yang lebih kecil dari dirinya sendiri di dalamnya.

Mengapa Menggunakan Fungsi Rekursif?

Anda mungkin berpikir, " Mengapa saya ingin sebuah fungsi memanggil dirinya sendiri? Bukan itu membingungkan?" Well, fungsi rekursif bisa sangat berguna untuk menyelesaikan masalah yang memiliki struktur berulang. Mereka bisa membuat kode kita lebih elegan dan mudah dipahami untuk jenis masalah tertentu.

mari kita lihat contoh sederhana untuk merasakan:

function countDown($n) {
if ($n <= 0) {
echo "Blastoff!";
} else {
echo $n . "... ";
countDown($n - 1);
}
}

countDown(5);

Jika kita menjalankan fungsi ini dengan countDown(5), ini apa yang terjadi:

  1. Itu mencetak "5... "
  2. Kemudian memanggil dirinya sendiri dengan 4
  3. Mencetak "4... "
  4. Memanggil dirinya sendiri dengan 3
  5. Dan begitu seterusnya sampai mencapai 0 dan mencetak "Blastoff!"

Hasilnya akan adalah: "5... 4... 3... 2... 1... Blastoff!"

Anatomi Fungsi Rekursif

Setiap fungsi rekursif memiliki dua bagian utama:

  1. Kasus dasar: Ini adalah kondisi yang menghentikan rekursi. Tanpa ini, fungsi Anda akan terus memanggil dirinya sendiri (atau sampai komputer Anda kehabisan memori)!

  2. Kasus rekursif: Ini adalah tempat fungsi memanggil dirinya sendiri, biasanya dengan parameter yang diubah.

Dalam contoh countdown kami, if ($n <= 0) adalah kasus dasar, dan countDown($n - 1) adalah kasus rekursif.

Perhitungan Faktorial Menggunakan Rekursi

Sekarang kita sudah mengetahui dasarnya, mari kita hadapi masalah klasik: menghitung faktorial. Faktorial dari sebuah bilangan n (ditulis sebagai n!) adalah produk semua bilangan positif kurang dari atau sama dengan n.

Misalnya: 5! = 5 4 3 2 1 = 120

Ini adalah cara kita menghitung faktorial menggunakan rekursi:

function factorial($n) {
if ($n <= 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}

echo factorial(5); // Output: 120

mari kitauraikan ini:

  1. Kasus dasar kita adalah if ($n <= 1). Kita tahu bahwa 1! dan 0! keduanya sama dengan 1, jadi kita mengembalikan 1 dalam kasus ini.
  2. Untuk bilangan lain, kita kalikan $n dengan faktorial (n-1).

Ketika kita memanggil factorial(5), ini apa yang terjadi di belakang layar:

factorial(5) = 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

Apakah itu indah bagaimana fungsi ini terus memanggil dirinya sendiri sampai mencapai kasus dasar, dan kemudian hasilnya mengembalikan?

Pencarian Binary Menggunakan Rekursi

Sekarang, mari kita naik tingkat dan lihat contoh yang lebih kompleks: pencarian binary. Pencarian binary adalah algoritme yang efisien untuk menemukan item dari daftar yang diurutkan. Itu bekerja dengan terus membagi dalam setengah bagian daftar yang mungkin mengandung item, sampai Anda mengecilkan lokasi kemungkinan menjadi hanya satu.

Ini adalah cara kita implementasikan pencarian binary menggunakan rekursi:

function binarySearch($arr, $left, $right, $x) {
if ($right >= $left) {
$mid = $left + floor(($right - $left) / 2);

// Jika elemen ada di tengah sendiri
if ($arr[$mid] == $x) {
return $mid;
}

// Jika elemen lebih kecil dari tengah, maka itu hanya bisa ada di subarray kiri
if ($arr[$mid] > $x) {
return binarySearch($arr, $left, $mid - 1, $x);
}

// Jika tidak, elemen hanya bisa ada di subarray kanan
return binarySearch($arr, $mid + 1, $right, $x);
}

// Kita mencapai sini saat elemen tidak ada di array
return -1;
}

$arr = [2, 3, 4, 10, 40];
$x = 10;
$result = binarySearch($arr, 0, count($arr) - 1, $x);
echo ($result == -1) ? "Elemen tidak ada di array" : "Elemen ada di indeks " . $result;

Fungsi ini mungkin terlihat menakutkan pada awalnya, tapi mari kitauraikan:

  1. Kita mulai dengan memeriksa jika indeks kanan lebih besar atau sama dengan indeks kiri. Ini adalah kondisi lanjutan kita.
  2. Kita menghitung indeks tengah.
  3. Jika elemen tengah adalah target kita, kita selesai!
  4. Jika elemen tengah lebih besar dari target kita, kita secara rekursif mencari di subarray kiri.
  5. Jika elemen tengah lebih kecil dari target kita, kita secara rekursif mencari di subarray kanan.
  6. Jika kita menghabiskan pencarian kita (kanan < kiri), kita kembalikan -1 untuk menandakan elemen tidak ditemukan.

Keindahan pendekatan rekursif ini adalah bagaimana ia secara alami membagi masalah menjadi submasalah yang lebih kecil, membuat kode elegan dan mudah dipahami saat Anda memahami konsepnya.

Kesimpulan

Fungsi rekursif mungkin terlihat agak membingungkan pada awalnya, tapi mereka adalah alat yang sangat kuat dalam peralatan pemrogram. Mereka memungkinkan kita untuk menyelesaikan masalah kompleks dengan kode yang elegan dan ringkas. Seperti biasa, Anda akan mulai mengenali masalah yang cocok untuk solusi rekursif saat Anda berlatih lebih banyak.

Ingat, seperti semua alat yang kuat, rekursi harus digunakan dengan hati-hati. Kadang-kadang, solusi iteratif mungkin lebih efisien atau mudah dipahami. Dengan pengalaman yang semakin bertambah, Anda akan mengembangkan intuisi tentang kapan menggunakan rekursi dan kapan menggunakan pendekatan lain.

Terus coding, terus eksperimen, dan terutama, bersenang-senang! Pemrograman adalah seni serta ilmu, dan memahami konsep seperti rekursi akan membantu Anda menciptakan kode yang indah dan efisien. Sampai jumpa lagi, coding yang menyenangkan!

Credits: Image by storyset