Bagaimana Rekursi Bekerja - Dijelaskan dengan Diagram Alir dan Video

"Untuk memahami rekursi, pertama-tama orang harus memahami rekursi."

Rekursi bisa jadi sulit untuk dipahami - terutama bagi programmer baru. Dalam bentuknya yang paling sederhana, fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Izinkan saya mencoba menjelaskan dengan sebuah contoh.

Bayangkan Anda pergi untuk membuka pintu kamar tidur Anda dan pintu itu terkunci. Putra Anda yang berusia tiga tahun muncul dari sekitar sudut dan memberi tahu Anda bahwa dia menyembunyikan satu-satunya kunci di dalam sebuah kotak. ("Sama seperti dia," menurut Anda.) Anda terlambat bekerja dan Anda benar-benar perlu masuk ke kamar untuk mengambil baju Anda.

Anda membuka kotak hanya untuk menemukan… kotak lainnya. Kotak di dalam kotak. Dan Anda tidak tahu mana yang memiliki kuncinya! Anda perlu segera mendapatkan kemeja itu, jadi Anda harus memikirkan algoritme yang baik untuk menemukan kunci itu.

Ada dua pendekatan utama untuk membuat algoritma untuk masalah ini: iteratif dan rekursif. Berikut kedua pendekatan tersebut sebagai diagram alir:

Pendekatan mana yang tampaknya lebih mudah bagi Anda?

Pendekatan pertama menggunakan loop sementara. Meskipun tumpukannya tidak kosong, ambil sebuah kotak dan lihat ke dalamnya. Berikut beberapa pseudocode yang terinspirasi JavaScript yang menunjukkan apa yang terjadi. (Pseudocode ditulis seperti kode, tetapi dimaksudkan agar lebih seperti ucapan manusia.)

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

Cara kedua menggunakan rekursi. Ingat, rekursi adalah tempat fungsi memanggil dirinya sendiri. Berikut cara kedua dalam pseudocode.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Kedua pendekatan tersebut mencapai hal yang sama. Tujuan utama menggunakan pendekatan rekursif adalah bahwa begitu Anda memahaminya, maka bisa lebih jelas untuk dibaca. Sebenarnya tidak ada manfaat kinerja untuk menggunakan rekursi. Pendekatan iteratif dengan loop terkadang bisa lebih cepat. Tetapi terutama kesederhanaan rekursi terkadang lebih disukai.

Selain itu, karena banyak algoritme menggunakan rekursi, penting untuk memahami cara kerjanya. Jika rekursi masih tidak mudah bagi Anda, jangan khawatir: Saya akan membahas beberapa contoh lagi.

Kasus dasar dan kasus rekursif

Sesuatu yang harus Anda perhatikan saat menulis fungsi rekursif adalah loop tak terbatas. Ini terjadi ketika fungsi terus memanggil dirinya sendiri ... dan tidak pernah berhenti memanggil dirinya sendiri!

Misalnya, Anda mungkin ingin menulis fungsi hitung mundur. Anda bisa menulisnya secara rekursif dalam JavaScript seperti ini:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Fungsi ini akan terus menghitung mundur selamanya. Jika Anda menjalankan kode secara tidak sengaja dengan loop tak terbatas, Anda dapat menekan "Ctrl-C" untuk mematikan skrip Anda. (Atau, jika Anda terkadang menggunakan CodePen seperti saya, Anda harus menambahkan “? Turn_off_js = true” di akhir URL.)

Fungsi rekursif selalu mengatakan kapan harus berhenti berulang. Harus selalu ada dua bagian untuk fungsi rekursif: kotak rekursif dan kotak dasar. Kasus rekursif adalah ketika fungsi memanggil dirinya sendiri. Kasus dasarnya adalah ketika fungsi berhenti memanggil dirinya sendiri. Ini mencegah loop tak terbatas.

Ini adalah fungsi hitung mundur lagi, dengan kasus dasar:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

Mungkin tidak jelas persis apa yang terjadi dalam fungsi ini. Saya akan menjelaskan apa yang terjadi saat Anda memanggil fungsi hitung mundur dengan meneruskan "5".

Kami mulai dengan mencetak angka 5 menggunakan console.log. Karena lima tidak kurang dari atau sama dengan nol, kita pergi ke pernyataan else. Di sana kita memanggil fungsi hitung mundur lagi dengan angka empat (5–1 = 4?).

Kami log jumlah 4. Sekali lagi, iini tidak kurang atau sama dengan nol sehingga kami pergi ke lain pernyataan dan panggilan hitung mundur dengan 3. Ini terus berlanjut sampaiisama dengan nol. Ketika itu terjadi, kita log angka nol dan kemudian iadalah kurang dari atau sama dengan nol. Kami akhirnya sampai ke pernyataan return dan keluar dari fungsi.

The Call Stack

Fungsi rekursif menggunakan sesuatu yang disebut "tumpukan panggilan". Ketika sebuah program memanggil suatu fungsi, fungsi itu berada di atas tumpukan panggilan. Ini mirip dengan setumpuk buku. Anda menambahkan sesuatu satu per satu. Kemudian, saat Anda siap melepas sesuatu, Anda selalu melepas barang teratas.

Saya akan menunjukkan kepada Anda tumpukan panggilan beraksi dengan factorialfungsi tersebut. factorial(5)ditulis sebagai 5! dan itu didefinisikan seperti ini: 5! = 5 * 4 * 3 * 2 * 1. Berikut adalah fungsi rekursif untuk menghitung faktorial sebuah bilangan:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Sekarang mari kita lihat apa yang terjadi jika Anda memanggil fact(3)Ilustrasi di bawah ini menunjukkan bagaimana tumpukan berubah, baris demi baris. Kotak paling atas di tumpukan memberi tahu Anda panggilan apa yang factsedang Anda lakukan.

Perhatikan bagaimana setiap panggilan ke factmemiliki salinannya sendiri x. Ini sangat penting untuk membuat pekerjaan rekursi. Anda tidak dapat mengakses salinan dari fungsi lain x.

Apakah Anda sudah menemukan kuncinya?

Mari secara singkat kembali ke contoh asli tentang mencari di kotak bersarang untuk sebuah kunci. Ingat, metode pertama adalah berulang menggunakan loop. Dengan cara tersebut, Anda membuat tumpukan kotak untuk dicari, sehingga Anda selalu tahu kotak apa yang masih perlu Anda cari.

Tetapi tidak ada tumpukan dalam pendekatan rekursif. Bagaimana algoritme Anda mengetahui kotak mana yang masih harus Anda cari? "Tumpukan kotak" disimpan di tumpukan. Ini adalah tumpukan panggilan fungsi yang setengah selesai, masing-masing dengan daftar kotaknya sendiri yang setengah lengkap untuk dilihat. Tumpukan melacak tumpukan kotak untuk Anda!

Dan berkat rekursi, Anda akhirnya bisa menemukan kunci dan mendapatkan baju Anda!

Anda juga dapat menonton video 5 menit yang saya buat tentang rekursi. Ini harus memperkuat konsep rekursi ini.

Kesimpulan

Saya harap artikel ini memberi Anda lebih banyak kejelasan tentang rekursi dalam pemrograman. Artikel ini didasarkan pada pelajaran dalam kursus video baru saya dari Manning Publications yang berjudul Algorithms in Motion. Kursus (dan juga artikel ini) didasarkan pada buku Algoritma Grokking yang menakjubkan oleh Adit Bhargava. Dialah yang menggambar semua ilustrasi menyenangkan di artikel ini.

Jika Anda belajar paling baik melalui buku, dapatkan bukunya! Jika Anda belajar terbaik melalui video, pertimbangkan untuk membeli kursus saya.

Dapatkan diskon 39% untuk kursus saya dengan menggunakan kode ' 39carnes '!

Dan akhirnya, untuk benar-benar memahami rekursi, Anda harus membaca artikel ini lagi. ?