pengertian dan implementasi Rekursi/Rekursif

Posted on 4:40 PM by Rudi Syaifudin

Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer. Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa.

Rekursi

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.