Home > Algorithm > Rekursif

Rekursif


Definisi rekursif 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.

Rekursif 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).

Ada algoritma sederhana yang bisa digunakan untuk mencari suatu item pada array : Lihat setiap array, dan cek apakah isinya sama dengan item yang kita cari. Jika ketemu, maka pencarian selesai. Jika kita sudah melihat semua item dan tidak ada item yang sama, maka kita yakin bahwa item yang kita cari tidak ada dalam array.

Subrutin untuk mengimplementasikan algoritma tersebut mudah kita tulis. Misalnya array yang kita cari bertipe int[]. Berikut ini adalah metode untuk mencari integer tertentu dalam array. Jika integer ditemukan, maka metode ini akan mengembalikan indeks dalam array di mana item tersebut ditemukan. Jika integer tersebut tidak ada dalam array, maka metode tersebut akan mengembalikan nilai -1, yang artinya integer tersebut tidak ditemukan.

static int cari(int[] A, int N) {
    for (int indeks = 0; indeks < A.length; indeks++) {
        if ( A[indeks] == N )
            return indeks;
    }
    return -1;
}

Metode seperti ini dimana pencarian dilakukan dengan menguji setiap item disebut pencarian linier (linear search). Jika kita tidak mengetahui apa-apa tentang isi dan urutan item pada array, maka tidak ada lagi algoritma alternatif yang lebih baik dari ini. Akan tetapi jika kita tahu bahwa elemen di dalam array diurut dalam urutan menaik atau urutan menurun, maka kita bisa menggunakan algoritma lain yang lebih cepat. Tentu saja, waktu yang dibutuhkan untuk mengurutkan array tidak sebentar, akan tetapi jika array ini akan dicari berulang kali, maka waktu pengurutan array akan terbayarkan dengan cepat.

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.

Source : Belajar Java

Categories: Algorithm Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: