Definisi rekursi adalah definisi yang menggunakan konsep atau sebagian dari definisi tersebut menjadi definisi yang komplit.
Misalnya : "keturunan" bisa berarti anak atau keturunan dari anak. "Kalimat" bisa berarti dua kalimat yang digabung dengan kata hubung "dan". "Direktori" adalah bagian pada hard disk yang berisi file dan direktori. Dalam matematika, "himpunan" adalah koleksi elemen, di mana elemen tersebut bisa berupa himpunan. "Pernyataan" pada Java misalnya pernyataan while yang didalamnya terdapat kata while, kondisi bernilai boolean dan pernyataan lainnya.
Definisi rekursi bisa menjelaskan situasi yang sangat kompleks dalam beberapa kata. Definisi istilah "keturunan" tanpa menggunakan rekursi bisa jadi "anak, cucu, cicit, dan seterusnya". Akan tetapi mengatakan "dan seterusnya" bukan arti "keturunan" secara lengkap.
Kita juga akan kesulitan jika kita mencoba mendefinisikan "direktori" sebagai "file yang berisi daftar file, dimana beberapa file bisa berisi daftar file, di mana beberapa file tersebut bisa berisi daftar file, dan seterusnya". Mencoba untuk menjelaskan pernyataan Java tanpa menggunakan rekursi dalam definisinya akan sulit dilakukan.
Rekursi bisa digunakan dalam teknik pemrograman. Subrutin rekursif adalah subrutin yang memanggil dirinya sendiri, baik langsung maupun tak langsung. Subrutin tersebut memanggil dirinya sendiri secara tidak langsung yaitu jika ia memanggil subrutin lain yang akhirnya memanggil subrutin pertama (baik langsung maupun tak langsung).
Suatu subrutin rekursi bisa menyelesaikan tugas kompleks dalam beberapa baris perintah. Kita akan lihat beberapa contohnya pada bagian ini.
Mari kita mulai dengan contoh yang sudah kita lihat sebelumnya: algorithma pencarian biner pada bagian sebelumnya. Pencarian biner digunakan untuk mencari suatu nilai dalam list terurut (atau jika item nilai tersebut tidak ada di dalam list tersebut, akan memberitahu hasilnya misalnya dengan mengembalikan -1).
Caranya adalah dengan mengecek elemen di tengah list tersebut. Jika elemen tersebut sama dengan nilai yang dicari, maka pencarian tersebut selesai. Jika nilai yang dicari lebih kecil daripada nilai elemen di tengah list tersebut, maka kita harus mencari di separuh awal dari list tersebut. Jika lebih besar, kita harus mencari di separuh akhir list tersebut. Kemudian, pada separuh list yang kita pilih tersebut, kita akan mengecek kembali elemen tengahnya. Kita akan melihat kembali apakah nilainya sama dengan nilai yang kita cari, lebih besar atau lebih kecil, yang dari sini kita tahu paruh mana yang akan kita cari berikutnya. Dan begitu seterusnya, hingga besar list yang akan dicari berkurang menjadi 0.
Ini adalah definisi rekursif, dan kita bisa membuat subrutin rekursif untuk mengimplementasikannya.
Sebelumnya, ada dua pertimbahangan yang harus kita masukkan ke dalam perhitungan kita, yang merupakan fakta tentang subrutin rekursif. Pertama, algoritma pencarian biner dimulai dengan mengecek "elemen tengah suatu list". Apa yang terjadi jika list tersebut kosong? Jika tidak ada elemen di dalam list, maka kita tidak mungkin melihat elemen di tengahnya. Atau dengan kata lain, ini disebut "kondisi awal" untuk mengecek elemen di tengah list, yaitu memiliki list yang tidak kosong.
Apa yang terjadi kita ternyata harus mencari nilai di list kosong? Jawabannya mudah : Kita bisa mengatakan bahwa nilai yang kita cari tidak ada di dalam list. List kosong adalah kasus dasar untuk algoritma pencari biner. Kasus dasar untuk algoritma rekursif adalah kasus yang akan ditangani secara langsung, bukan dilakukan secara rekursif. Algoritma pencarian biner memiliki kasus dasar lain, yaitu jika kita menemukan nilai yang kita cari di tengah suatu list, maka program tersebut selesai. Kita tidak perlu melakukan rekursi lebih lanjut.
Pertimbangan kedua adalah parameter subrutin tersebut. Dalam subrutin non-rekursif dari pencarian biner yang dibahas sebelumnya, parameternya adalah suatu array. Akan tetapi dalam pendekatan rekursif, kita harus bisa menerapkan subrutin secara rekursif hanya sebagian dari list aslinya. Pada subrutin aslinya yang non-rekursif, kita melakukan pencarian di seluruh array, sedangkan subrutin rekursif harus bisa mencari di sebagian array. Parameter subrutin tersebut harus bisa memberi tahu di bagian mana array akan dicari.
Berikut ini adalah algoritma pencarian biner rekursif yang mencari suatu nilai dalam bagian dari array integer:
Dalam rutin di atas, parameter idksRendah dan idksTinggi menyatakan bagian array yang akan dicari. Untuk mencari keseluruhan array, kita hanya perlu memanggil cariBiner(A, 0, A.length - 1, nilai). Dalam kedua kasus dasar -- yaitu tidak ada elemen di dalam rentang indeks yang diberikan dan ketika tidak ada nilai yang ditemukan di tengah-tengah rentang tersebut -- subrutin dapat memberikan jawabannya secara langsung, tanpa rekursi. Pada kasus lain, subrutin akan memanggil dirinya sendiri secara rekursif untuk menghitung dan mengembalikan hasilnya.
Banyak orang yang merasa sulit untuk memahami bagaimana rekursi bekerja. Kuncinya ada 2 hal yang harus dipenuhi agar rekursi bisa bekerja dengan benar :
- Harus ada minimum satu kasus dasar, yang bisa ditangani tanpa menggunakan rekursi.
- Jika subrutin dilakukan secara rekursif, ia harus dipanggil dalam lingkup yang lebih kecil, makin kecil hingga mendekati kasus dasarnya.
Satu kesalahan umum yang terjadi ketika menulis subrutin rekursif adalah jika kita melanggar salah satu dari kedua aturan di atas. Jika aturan ini dilanggar, hasilnya bisa jadi rekursi tak hingga, di mana subrutin tersebut akan memanggil dirinya terus menerus tanpa henti, karena tidak pernah mencapai kasus dasarnya.
Rekrusi tak hingga mirip dengan perulangan yang tak pernah berhenti. Akan tetapi karena setiap panggilan rekursif menggunakan memori komputer, maka program yang tersangkut di dalam rekursi tak hingga, pada akhirnya akan kehabisan memori.
Pencarian biner dapat diimplementasikan dengan perulangan while selain dengan menggunakan rekursi. Sekarang mari kita lihat suatu masalah yang lebih mudah diselesaikan dengan rekursi tapi sulit dilakukan dengan metode lain. Berikut ini adalah contoh yang biasa digunakan, yand dinamakan "Menara Hanoi".
Persoalannya dapat dituliskan sebagai berikut : sebuah tumpukan piringan dengan ukuran berbeda ditumpuk dari urutan terbesar di bagian paling bawah hingga terkecil di bagian paling atas. Seluruh piringan harus dipindahkan dari satu tiang ke tiang lain, dengan dua aturan :
- dalam setiap langkah hanya boleh memindahkan satu piringan, dan
- piringan yang lebih besar tidak boleh diletakkan di atas piringan yang lebih kecil.
Ada tiang lain yang berfungsi sebagai tiang cadangan, dan bisa digunakan sebagai tempat sementara. Gambar berikut (atas) mengilustrasikan tumpukan 10 piringan. Gambar lainnya (bawah) adalah ilustrasi setelah beberapa langkah telah dijalankan.
Kita akan memindahkan 10 piringan dari tiang 0 ke tiang 1, dan tiang 2 bisa dijadikan cadangan. Bisakah kita mengurangi persoalan ini menjadi persoalan yang sama dengan skala yang lebih kecil? Mungkin kita harus sedikit mengeneralisir persoalannya sehingga kita bisa melihat lebih jelas.
Jika ada N piringan pada tiang 0, kita tahu bahwa pada akhirnya kita haris memindahkan piringan paling bawah dari tiang 0 ke tiang 1. Akan tetapi sebelum itu, menurut aturan di atas, piringan 0 hingga N-1 harus dipindahkan terlebih dahulu ke tiang 2. Setelah kita pindahkan piringan ke-N ke tiang 1, maka kita harus memindahkan kembali N-1 piringan dari tiang 2 ke tiang 1 untuk menyelesaikan masalahnya. Lihat bahwa memindahkan N-1 piringan adalah persoalan yang sama seperti memindahkan N piringan, akan tetapi sekarang persoalannya menjadi lebih kecil.
Ini bisa dilakukan dengan mudah dengan rekursi.
Suatu persoalan harus digeneralisir terlebih dahulu, di sini kita lihat bahwa persoalan yang lebih kecil adalah memindahkan piringan dari tiang 0 ke tiang 2 dan kemudian dari tiang 2 ke tiang 1, bukan dari tiang 0 ke tiang 1. Untuk subrutin rekursiif yang akan kita buat, kita harus menyatakan tiang asal, tiang tujuan, dan tiang cadangannya. Kasus dasarnya adalah jika hanya ada satu piringan yang akan dipindahkan, yang mana jawabannya mudah : pindahkan satu piringan itu dalam satu langkah.
Berikut ini adalah contoh subrutin untuk menyelesaikan masalah ini :
Subrutin ini mengekspresikan solusi persoalan secara alami. Rekursi bisa bekerja dengan benar karena setiap panggil rekursif selalu akan dipanggil dengan jumlah piringan yang semakin sedikit. Dan ketika sampai pada kasus dasarnya, yaitu hanya ada satu piringan, persoalannya bisa diselesaikan langsung dengan memindahkan satu piringan tersebut ke tiang tujuannya.
Untuk memecahkan persoalan ini pada "level paling atas", yaitu memindahkan N piringan dari tiang 0 ke tiang 1, subrutin ini bisa dipanggil dengan perintah MenaraHanoi(N,0,1,2).
Ceritanya, dahulu kala ada kisah yang merupakan nama dari persoalan ini. Menurut cerita ini, pada saat bumi pertama kali dicipkatan, sekumpulan biksu pada suatu menara di dekat Hanoi diberi tumpukan 64 piringan dan diberi tugas untuk memindahkan satu piringan setiap hari dengan aturan yang sama seperti di atas. Pada hari ketika tugas ini selesai, alam semesta akan kiamat. Tapi tenang saja, karena jumlah langkah yang diperlukan untuk menyelesaikan tugas ini untuk N piringan adalah 2N - 1, dan 264 - 1 hari sama dengan lebih dari 50 trilyun tahun.
Misalnya : "keturunan" bisa berarti anak atau keturunan dari anak. "Kalimat" bisa berarti dua kalimat yang digabung dengan kata hubung "dan". "Direktori" adalah bagian pada hard disk yang berisi file dan direktori. Dalam matematika, "himpunan" adalah koleksi elemen, di mana elemen tersebut bisa berupa himpunan. "Pernyataan" pada Java misalnya pernyataan while yang didalamnya terdapat kata while, kondisi bernilai boolean dan pernyataan lainnya.
Definisi rekursi bisa menjelaskan situasi yang sangat kompleks dalam beberapa kata. Definisi istilah "keturunan" tanpa menggunakan rekursi bisa jadi "anak, cucu, cicit, dan seterusnya". Akan tetapi mengatakan "dan seterusnya" bukan arti "keturunan" secara lengkap.
Kita juga akan kesulitan jika kita mencoba mendefinisikan "direktori" sebagai "file yang berisi daftar file, dimana beberapa file bisa berisi daftar file, di mana beberapa file tersebut bisa berisi daftar file, dan seterusnya". Mencoba untuk menjelaskan pernyataan Java tanpa menggunakan rekursi dalam definisinya akan sulit dilakukan.
Rekursi bisa digunakan dalam teknik pemrograman. Subrutin rekursif adalah subrutin yang memanggil dirinya sendiri, baik langsung maupun tak langsung. Subrutin tersebut memanggil dirinya sendiri secara tidak langsung yaitu jika ia memanggil subrutin lain yang akhirnya memanggil subrutin pertama (baik langsung maupun tak langsung).
Suatu subrutin rekursi bisa menyelesaikan tugas kompleks dalam beberapa baris perintah. Kita akan lihat beberapa contohnya pada bagian ini.
Mari kita mulai dengan contoh yang sudah kita lihat sebelumnya: algorithma pencarian biner pada bagian sebelumnya. Pencarian biner digunakan untuk mencari suatu nilai dalam list terurut (atau jika item nilai tersebut tidak ada di dalam list tersebut, akan memberitahu hasilnya misalnya dengan mengembalikan -1).
Caranya adalah dengan mengecek elemen di tengah list tersebut. Jika elemen tersebut sama dengan nilai yang dicari, maka pencarian tersebut selesai. Jika nilai yang dicari lebih kecil daripada nilai elemen di tengah list tersebut, maka kita harus mencari di separuh awal dari list tersebut. Jika lebih besar, kita harus mencari di separuh akhir list tersebut. Kemudian, pada separuh list yang kita pilih tersebut, kita akan mengecek kembali elemen tengahnya. Kita akan melihat kembali apakah nilainya sama dengan nilai yang kita cari, lebih besar atau lebih kecil, yang dari sini kita tahu paruh mana yang akan kita cari berikutnya. Dan begitu seterusnya, hingga besar list yang akan dicari berkurang menjadi 0.
Ini adalah definisi rekursif, dan kita bisa membuat subrutin rekursif untuk mengimplementasikannya.
Sebelumnya, ada dua pertimbahangan yang harus kita masukkan ke dalam perhitungan kita, yang merupakan fakta tentang subrutin rekursif. Pertama, algoritma pencarian biner dimulai dengan mengecek "elemen tengah suatu list". Apa yang terjadi jika list tersebut kosong? Jika tidak ada elemen di dalam list, maka kita tidak mungkin melihat elemen di tengahnya. Atau dengan kata lain, ini disebut "kondisi awal" untuk mengecek elemen di tengah list, yaitu memiliki list yang tidak kosong.
Apa yang terjadi kita ternyata harus mencari nilai di list kosong? Jawabannya mudah : Kita bisa mengatakan bahwa nilai yang kita cari tidak ada di dalam list. List kosong adalah kasus dasar untuk algoritma pencari biner. Kasus dasar untuk algoritma rekursif adalah kasus yang akan ditangani secara langsung, bukan dilakukan secara rekursif. Algoritma pencarian biner memiliki kasus dasar lain, yaitu jika kita menemukan nilai yang kita cari di tengah suatu list, maka program tersebut selesai. Kita tidak perlu melakukan rekursi lebih lanjut.
Pertimbangan kedua adalah parameter subrutin tersebut. Dalam subrutin non-rekursif dari pencarian biner yang dibahas sebelumnya, parameternya adalah suatu array. Akan tetapi dalam pendekatan rekursif, kita harus bisa menerapkan subrutin secara rekursif hanya sebagian dari list aslinya. Pada subrutin aslinya yang non-rekursif, kita melakukan pencarian di seluruh array, sedangkan subrutin rekursif harus bisa mencari di sebagian array. Parameter subrutin tersebut harus bisa memberi tahu di bagian mana array akan dicari.
Berikut ini adalah algoritma pencarian biner rekursif yang mencari suatu nilai dalam bagian dari array integer:
static int cariBiner(int[] A, int idksRendah, int idksTinggi, int nilai) { // Cari "nilai" pada array "A" dari posisi "idksRendah" ke "idksTinggi", // Asumsinya adalah array diurut dalam urutan menaik // Jika nilai ditemukan kembalikan indeks pada array // dimana nilai tersebut berada. Jika tidak kembalikan -1 if (idksRendah > idksTinggi) { // Artinya list kosong karena seharusnya idksRendah lebih rendah // dari idksTinggi. "Nilai" tidak mungkin ada di list kosong. return -1; } else { // Cek elemen di tengah list. Jika nilai sama dengan isi elemen // tengah, maka kembalikan posisi tersebut. // Jika tidak, cari secara rekursif di awal atau akhir // dari setengah list int idksTengah = (idksRendah + idksTinggi) / 2; if (nilai == A[idksTengah]) return idksTengah; else if (nilai < A[idksTengah]) return cariBiner(A, idksRendah, idksTengah - 1, nilai); else // nilai > A[idksTengah] return cariBiner(A, idksTengah + 1, idksTinggi, nilai); } } // akhir cariBiner()
Dalam rutin di atas, parameter idksRendah dan idksTinggi menyatakan bagian array yang akan dicari. Untuk mencari keseluruhan array, kita hanya perlu memanggil cariBiner(A, 0, A.length - 1, nilai). Dalam kedua kasus dasar -- yaitu tidak ada elemen di dalam rentang indeks yang diberikan dan ketika tidak ada nilai yang ditemukan di tengah-tengah rentang tersebut -- subrutin dapat memberikan jawabannya secara langsung, tanpa rekursi. Pada kasus lain, subrutin akan memanggil dirinya sendiri secara rekursif untuk menghitung dan mengembalikan hasilnya.
Banyak orang yang merasa sulit untuk memahami bagaimana rekursi bekerja. Kuncinya ada 2 hal yang harus dipenuhi agar rekursi bisa bekerja dengan benar :
- Harus ada minimum satu kasus dasar, yang bisa ditangani tanpa menggunakan rekursi.
- Jika subrutin dilakukan secara rekursif, ia harus dipanggil dalam lingkup yang lebih kecil, makin kecil hingga mendekati kasus dasarnya.
Satu kesalahan umum yang terjadi ketika menulis subrutin rekursif adalah jika kita melanggar salah satu dari kedua aturan di atas. Jika aturan ini dilanggar, hasilnya bisa jadi rekursi tak hingga, di mana subrutin tersebut akan memanggil dirinya terus menerus tanpa henti, karena tidak pernah mencapai kasus dasarnya.
Rekrusi tak hingga mirip dengan perulangan yang tak pernah berhenti. Akan tetapi karena setiap panggilan rekursif menggunakan memori komputer, maka program yang tersangkut di dalam rekursi tak hingga, pada akhirnya akan kehabisan memori.
Persoalannya dapat dituliskan sebagai berikut : sebuah tumpukan piringan dengan ukuran berbeda ditumpuk dari urutan terbesar di bagian paling bawah hingga terkecil di bagian paling atas. Seluruh piringan harus dipindahkan dari satu tiang ke tiang lain, dengan dua aturan :
- dalam setiap langkah hanya boleh memindahkan satu piringan, dan
- piringan yang lebih besar tidak boleh diletakkan di atas piringan yang lebih kecil.
Ada tiang lain yang berfungsi sebagai tiang cadangan, dan bisa digunakan sebagai tempat sementara. Gambar berikut (atas) mengilustrasikan tumpukan 10 piringan. Gambar lainnya (bawah) adalah ilustrasi setelah beberapa langkah telah dijalankan.
Kita akan memindahkan 10 piringan dari tiang 0 ke tiang 1, dan tiang 2 bisa dijadikan cadangan. Bisakah kita mengurangi persoalan ini menjadi persoalan yang sama dengan skala yang lebih kecil? Mungkin kita harus sedikit mengeneralisir persoalannya sehingga kita bisa melihat lebih jelas.
Jika ada N piringan pada tiang 0, kita tahu bahwa pada akhirnya kita haris memindahkan piringan paling bawah dari tiang 0 ke tiang 1. Akan tetapi sebelum itu, menurut aturan di atas, piringan 0 hingga N-1 harus dipindahkan terlebih dahulu ke tiang 2. Setelah kita pindahkan piringan ke-N ke tiang 1, maka kita harus memindahkan kembali N-1 piringan dari tiang 2 ke tiang 1 untuk menyelesaikan masalahnya. Lihat bahwa memindahkan N-1 piringan adalah persoalan yang sama seperti memindahkan N piringan, akan tetapi sekarang persoalannya menjadi lebih kecil.
Ini bisa dilakukan dengan mudah dengan rekursi.
Suatu persoalan harus digeneralisir terlebih dahulu, di sini kita lihat bahwa persoalan yang lebih kecil adalah memindahkan piringan dari tiang 0 ke tiang 2 dan kemudian dari tiang 2 ke tiang 1, bukan dari tiang 0 ke tiang 1. Untuk subrutin rekursiif yang akan kita buat, kita harus menyatakan tiang asal, tiang tujuan, dan tiang cadangannya. Kasus dasarnya adalah jika hanya ada satu piringan yang akan dipindahkan, yang mana jawabannya mudah : pindahkan satu piringan itu dalam satu langkah.
Berikut ini adalah contoh subrutin untuk menyelesaikan masalah ini :
void MenaraHanoi(int piringan, int asal, int tujuan, int cadangan) { // Memecahkan persoalan untuk memindahkan sejumlah "piringan" // dari tiang "asal" ke tiang "tujuan". Tiang "cadangan" bisa // digunakan sebagai tempat sementara if (piringan == 1) { // Hanya ada satu piringan, pindahkan langsung System.out.println("Pindahkan piringan dari tiang " + asal + " ke tiang " + tujuan); } else { // Pindahkan semua piringan minus 1 ke tiang cadangan, // kemudian pindahkan piringan paling bawah ke tiang tujuan, // kemudian pindahkan sisanya dari tiang cadangan ke // tiang tujuan. MenaraHanoi(piringan-1, asal, cadangan, tujuan); System.out.println("Pindahkan piringan dari tiang " + asal + " ke tiang " + tujuan); MenaraHanoi(piringan-1, cadangan, tujuan, asal); } }
Subrutin ini mengekspresikan solusi persoalan secara alami. Rekursi bisa bekerja dengan benar karena setiap panggil rekursif selalu akan dipanggil dengan jumlah piringan yang semakin sedikit. Dan ketika sampai pada kasus dasarnya, yaitu hanya ada satu piringan, persoalannya bisa diselesaikan langsung dengan memindahkan satu piringan tersebut ke tiang tujuannya.
Untuk memecahkan persoalan ini pada "level paling atas", yaitu memindahkan N piringan dari tiang 0 ke tiang 1, subrutin ini bisa dipanggil dengan perintah MenaraHanoi(N,0,1,2).
Ceritanya, dahulu kala ada kisah yang merupakan nama dari persoalan ini. Menurut cerita ini, pada saat bumi pertama kali dicipkatan, sekumpulan biksu pada suatu menara di dekat Hanoi diberi tumpukan 64 piringan dan diberi tugas untuk memindahkan satu piringan setiap hari dengan aturan yang sama seperti di atas. Pada hari ketika tugas ini selesai, alam semesta akan kiamat. Tapi tenang saja, karena jumlah langkah yang diperlukan untuk menyelesaikan tugas ini untuk N piringan adalah 2N - 1, dan 264 - 1 hari sama dengan lebih dari 50 trilyun tahun.
Tidak ada komentar:
Posting Komentar