Rabu, 05 Februari 2014
ass, kali ini saya akan berbagi ilmu tentang pelajaran struktur data yaitu REKURSIF, materi ini saya dapatkan ketika saya belajar di semester 2, semoga bermanfaat walaupun hanya sedikit
REKURSIF
Pengertian Rekursif
Rekursif berarti bahwa suatu proses bisa memanggil
dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf, Rekursif
adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif
sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa
rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus
dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik
pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan
proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri
bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.
Contoh paling sederhana dari proses
rekursif ini adalah proses menghitung nilai factorial dari suatu bilangan bulat
positif dan mencari deret Fibbonacci dari suatu bilangan bulat.
- Nilai factorial secara rekursif dapat ditulis sebagai
0 ! = 1
N ! = N x (N-1) !
yang secara pemrograman dapat ditulis sebagai
Faktorial(0)
= 1 (1)
Faktorial(N) = N*Faktorial(N-1) (2)
Persamaan (2) di atas adalah contoh hubungan rekurens (recurrence
relation), yang berarti bahwa nilai suatu fungsi dengan argumen tertentu
bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil. Persamaan
(1) tidak bersifat rekursif, disebut nilai awal atau basis. Setiap fungsi
rekursif paling sedikit mempunyai satu
nilai awal, jika tidak fungsi tersebut tidak bisa dihitung secara eksplisit.
- Bilangan Fibbonacci didefinisikan sebagai berikut
1
1 2 3
5 8 13
21 34 55
89 …
dari barisan tersebut dapat dilihat bahwa bilangan ke-N (N>2)
dalam barisan dapat dicari dari dua bilangan sebelumnya yang terdekat dengan
bilangan N, yaitu bilangan ke-(N-1) dan bilangan ke-(N-2), sehingga dapat
dirumuskan sebagai
Fibbonacci(1) = 1 (1)
Fibbonacci(2) = 1 (2)
Fibbonacci(N) = Fibbonacci(N-1) + Fibbonacci(N-2) (3)
Dengan
persamaan (1) dan (2) adalah basis dan persamaan (3) adalah rekurensnya
Rekursif Versus Iteratif
Dalam beberapa
situasi, pemecahan secara rekursif maupun secara iteratif mempunyai keuntungan
dan kekurangan yang bisa saling diperbandingkan. Adalah cukup sulit untuk
menentukan mana yang paling sederhana, paling jelas, paling efisien dan paling mudah
disbanding yang lain. Boleh dikatakan pemilihan cara iterative maupun rekursif
merupakan kesenangan seorang programmer dan tergantung konteks permasalahan
yang akan dipecahkan sesuai dengan kesanggupan yang bersangkutan.
Perhatikanlah
contoh berikut :
Contoh 1.
function FACT(N : integer) ® integer
{mengirimkan bilangan factorial
dengan cara rekursif}
Deklarasi
Deskripsi
if
(N=0) then
return
1 {Basis}
else
return(N*FACT(N-1)) {Rekurens}
endif
Contoh 2.
function FIBO(N : integer) ® integer
{mengirimkan bilangan fibbonacci
dengan cara rekursif}
Deklarasi
Deskripsi
if ((N=1) or (N=2)) then
return
1 {Basis}
else
return(FIBO(N-1)+
FIBO(N-2)) {Rekurens}
endif
Contoh 3.
function FACT(N : integer) ® integer
{mengirimkan bilangan factorial
dengan cara iteratif}
Deklarasi
x,i : integer
Deskripsi
x ¬ 1
for i = 1 to N do
x ¬ i*x
endfor
return
x
Contoh 4.
function FIBO(N : integer) ® integer
{mengirimkan bilangan fibbonacci
dengan cara iteratif}
Deklarasi
Fibbonacci,
Akhir, Bantu, i : integer
Deskripsi
If N=0 then
return
0
else
i¬1
Fibbonacci ¬1
Akhir ¬0
while (i¹N)do
Bantu
¬ Fibbonacci
i
¬ i + 1
Fibbonacci
¬ Fibbonacci + Akhir
Akhir
¬ Bantu
Endwhile
return
Fibbonacci
endif
