Rekursi dalam Struktur Data: Cara Kerja, Jenis & Kapan Digunakan

Diterbitkan: 2020-05-22

Mari kita mulai dengan definisi rekursi dalam struktur data. Kami kemudian akan membahas berbagai jenis rekursi dan bagaimana rekursi digunakan untuk memecahkan masalah yang berbeda.

Daftar isi

Apa itu rekursi?

Dengan kata sederhana, rekursi adalah pemecahan masalah, dan dalam beberapa kasus, teknik pemrograman yang memiliki properti yang sangat khusus dan eksklusif. Dalam rekursi, suatu fungsi atau metode memiliki kemampuan untuk memanggil dirinya sendiri untuk memecahkan masalah. Proses rekursi melibatkan pemecahan masalah dengan mengubahnya menjadi varietas yang lebih kecil dari dirinya sendiri.

Proses di mana suatu fungsi memanggil dirinya sendiri dapat terjadi secara langsung maupun tidak langsung. Perbedaan panggilan ini menimbulkan berbagai jenis rekursi, yang akan kita bicarakan nanti. Beberapa masalah yang dapat diselesaikan dengan menggunakan rekursi antara lain DFS of Graph, Towers of Hanoi, Different Types Tree Traversals, dan lain-lain. Untuk mempelajari tentang rekursi dan konsep ilmu data lainnya, lihat kursus online ilmu data IIIT-B.

Baca: 13 Ide Proyek Struktur Data yang Menarik

Bagaimana cara kerja rekursi?

Konsep rekursi didirikan pada gagasan bahwa suatu masalah dapat diselesaikan dengan lebih mudah dan dalam waktu yang lebih singkat jika direpresentasikan dalam satu atau versi yang lebih kecil. Menambahkan kondisi dasar untuk menghentikan rekursi adalah bagian penting lain dari penggunaan algoritma ini untuk memecahkan masalah.

Tidak Diperlukan Pengalaman Pengkodean. Dukungan karir 360°. Diploma PG dalam Pembelajaran Mesin & AI dari IIIT-B dan upGrad.

Orang sering percaya bahwa tidak mungkin mendefinisikan suatu entitas menurut dirinya sendiri. Rekursi membuktikan bahwa teori itu salah. Dan jika teknik ini dilakukan dengan cara yang benar, itu bisa menghasilkan hasil yang sangat kuat. Mari kita lihat bagaimana rekursi bekerja dengan beberapa contoh. Apa itu kalimat? Ini dapat didefinisikan sebagai dua atau lebih kalimat yang digabungkan dengan bantuan konjungsi. Demikian pula, folder bisa menjadi perangkat penyimpanan yang digunakan untuk menyimpan file dan folder. Leluhur bisa menjadi orang tua dari satu dan nenek moyang dari anggota keluarga lain di pohon keluarga.

Rekursi membantu dalam mendefinisikan situasi kompleks menggunakan beberapa kata yang sangat sederhana. Bagaimana Anda biasanya mendefinisikan leluhur? Orang tua, kakek-nenek, atau kakek buyut. Ini bisa berlanjut. Demikian pula, mendefinisikan folder bisa menjadi tugas yang sulit. Itu bisa apa saja yang menyimpan beberapa file dan folder yang bisa menjadi file dan folder dengan haknya sendiri, dan ini bisa terus berlanjut. Inilah sebabnya mengapa rekursi membuat mendefinisikan situasi jauh lebih mudah dari biasanya.

Rekursi juga merupakan teknik pemrograman yang cukup baik. Subrutin rekursif didefinisikan sebagai subrutin yang secara langsung atau tidak langsung memanggil dirinya sendiri. Memanggil sebuah subrutin secara langsung menandakan bahwa definisi dari subrutin tersebut sudah memiliki pernyataan panggilan untuk memanggil subrutin yang telah ditentukan.

Di sisi lain, panggilan tidak langsung dari subrutin terjadi ketika subrutin memanggil subrutin lain, yang kemudian memanggil subrutin asli. Rekursi dapat menggunakan beberapa baris kode untuk menggambarkan tugas yang sangat kompleks. Mari kita sekarang mengalihkan perhatian kita ke berbagai jenis rekursi yang telah kita bahas.

Baca juga: 6 Bahasa Pemrograman Terbaik untuk Dipelajari

Jenis rekursi

Hanya ada dua jenis rekursi seperti yang telah disebutkan. Mari kita lihat bagaimana mereka berbeda satu sama lain. Rekursi langsung adalah cara yang lebih sederhana karena hanya melibatkan satu langkah memanggil fungsi atau metode asli atau subrutin. Di sisi lain, rekursi tidak langsung melibatkan beberapa langkah.

Panggilan pertama dilakukan oleh metode asli ke metode kedua, yang pada gilirannya memanggil metode asli. Rantai panggilan ini dapat menampilkan sejumlah metode atau fungsi. Dengan kata sederhana, kita dapat mengatakan bahwa selalu ada variasi kedalaman rekursi tidak langsung, dan variasi kedalaman ini tergantung pada jumlah metode yang terlibat dalam proses.

Rekursi langsung dapat digunakan untuk memanggil hanya satu fungsi dengan sendirinya. Di sisi lain, rekursi tidak langsung dapat digunakan untuk memanggil lebih dari satu metode atau fungsi dengan bantuan fungsi lain, dan itu juga, beberapa kali. Rekursi tidak langsung tidak membuat overhead sementara rekan langsungnya melakukannya.

Kapan rekursi digunakan?

Ada situasi di mana Anda dapat menggunakan rekursi atau iterasi. Namun, Anda harus selalu memilih solusi yang tampaknya paling alami untuk suatu masalah. Rekursi selalu merupakan pilihan yang cocok dalam hal abstraksi data. Orang sering menggunakan definisi rekursif untuk mendefinisikan data dan operasi terkait.

Dan tidak salah untuk mengatakan bahwa rekursi sebagian besar merupakan solusi alami untuk masalah yang terkait dengan implementasi operasi yang berbeda pada data. Namun, ada hal-hal tertentu yang terkait dengan rekursi yang mungkin tidak menjadikannya solusi terbaik untuk setiap masalah. Dalam situasi ini, alternatif seperti metode iteratif adalah yang paling cocok.

Implementasi rekursi menggunakan banyak ruang stack, yang seringkali dapat mengakibatkan redundansi. Setiap kali kami menggunakan rekursi, kami memanggil metode yang menghasilkan pembuatan instance baru dari metode itu. Instance baru ini membawa parameter dan variabel berbeda, yang disimpan di tumpukan, dan diambil saat kembali. Jadi sementara rekursi adalah solusi yang lebih sederhana daripada yang lain, biasanya bukan yang paling praktis.

Selain itu, kami tidak memiliki seperangkat aturan yang telah ditentukan sebelumnya yang dapat membantu memilih iterasi atau rekursi untuk masalah yang berbeda. Manfaat terbesar menggunakan rekursi adalah metode yang ringkas. Ini membuat membaca dan memeliharanya menjadi tugas yang lebih mudah dari biasanya. Tetapi metode rekursif bukanlah metode yang paling efisien yang tersedia bagi kami karena metode tersebut memakan banyak ruang penyimpanan dan menghabiskan banyak waktu selama implementasi.

Mengingat beberapa hal dapat membantu Anda memutuskan apakah memilih rekursi untuk suatu masalah adalah cara yang tepat untuk dilakukan atau tidak. Anda harus memilih rekursi jika masalah yang akan Anda pecahkan disebutkan dalam istilah rekursif dan solusi rekursif tampaknya kurang kompleks.

Anda harus tahu bahwa rekursi, dalam banyak kasus, menyederhanakan implementasi algoritme yang ingin Anda gunakan. Sekarang jika kompleksitas yang terkait dengan penggunaan iterasi dan rekursi sama untuk masalah yang diberikan, Anda harus menggunakan iterasi karena kemungkinannya menjadi lebih efisien lebih tinggi.

Baca juga: 23 Kursus Pemrograman Komputer Terbaik Untuk Mendapatkan Pekerjaan

Kesimpulan

Namun, mungkin ada situasi di mana membuat keputusan mungkin tidak semudah itu. Anda harus memilih antara efisiensi dan kesederhanaan. Jika Anda seorang desainer berpengalaman, Anda akan tahu persis kapan harus lebih mementingkan efisiensi dan ketika memilih kesederhanaan atau keringkasan di atasnya adalah cara yang harus dilakukan.

Jika Anda penasaran untuk mempelajari tentang struktur data, ilmu data, lihat Program PG Eksekutif IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan industri pakar, tatap muka dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.

Apa aplikasi rekursi kehidupan nyata yang paling umum?

Rekursi adalah proses di mana fungsi memanggil dirinya sendiri secara tidak langsung atau langsung untuk menyelesaikan masalah. Fungsi yang melakukan proses rekursi disebut fungsi rekursif. Ada masalah tertentu yang dapat diselesaikan dengan cukup mudah dengan bantuan algoritma rekursif.

Aplikasi rekursi kehidupan nyata yang paling umum adalah ketika Anda menghitung berapa banyak uang yang Anda miliki dalam sebuah kotak yang berisi Rs. 100 catatan. Jika ada terlalu banyak catatan, maka Anda bisa meminta teman Anda untuk melakukan pekerjaan yang sama dengan membagi seluruh tumpukan menjadi dua. Setelah Anda berdua selesai menghitung, Anda tinggal menjumlahkan kedua hasil untuk mendapatkan jumlah total.

Apa saja sifat-sifat yang harus dimiliki oleh fungsi rekursif?

Fungsi rekursif memiliki kemampuan untuk melanjutkan sebagai loop tak terbatas. Ada dua properti yang harus didefinisikan untuk setiap fungsi rekursif untuk mencegahnya masuk ke loop tak terbatas. Mereka:

1. Kriteria dasar – Harus ada satu kondisi dasar yang telah ditentukan sebelumnya. Setiap kali kriteria dasar ini terpenuhi, fungsi akan berhenti memanggil dirinya sendiri.
2. Pendekatan progresif – Panggilan rekursif harus terdiri dari pendekatan progresif. Setiap kali panggilan rekursif dibuat ke fungsi, itu harus mencapai dekat kondisi dasar.

Apa kelebihan dan kekurangan rekursi?

Beberapa keuntungan rekursi adalah Anda hanya perlu mendefinisikan kondisi dasar dan kasus rekursif dalam fungsi rekursif. Ini membuat kodenya cukup sederhana dan pendek dibandingkan dengan kode iteratif, dan beberapa masalah seperti Tree Traversal dan Graph secara inheren bersifat rekursif.

Kerugian terbesar dari rekursi adalah bahwa ada kebutuhan ruang yang lebih besar untuk fungsi rekursif dibandingkan dengan program iteratif karena setiap panggilan fungsi harus tetap berada di tumpukan sampai kondisi dasar terpenuhi, dan ada persyaratan waktu yang lebih besar juga, karena tumpukan tumbuh setelah setiap panggilan fungsi, dan jawaban akhir hanya dapat dikembalikan setelah mengeluarkan semua elemen dari tumpukan.