Rekursif
Apa yang dimaksud dengan Rekursif ?
Rekursif adalah teknik pemecahan masalah yang powerful dan dapat digunakan ketika inti dari masalah terjadi berulang kali. Tentu saja, tipe dari masalah ini dapat dipecahkan mengunakan perkataan berulang-ulang (yaitu, menggunakan konstruksi looping seperti for, while dan do-while).
Sesungguhnya, iterasi atau perkataan berulang-ulang merupakan peralatan yang lebih efisien jika dibandingkan dengan rekursif tetapi rekursif menyediakan solusi yang lebih baik untuk suatu masalah. Pada rekursif, method dapat memanggil dirinya sendiri. Data yang berada dalam method tersebut seperti argument disimpan sementara ke dalam stack sampai method pemanggilnya diselesaikan.
Rekursif vs. Iterasi
Untuk pengertian yang lebih baik dari rekursif, mari kita lihat pada bagaimana macammacam dari teknik iterasi. Dalam teknik-teknik tersebut juga dapat kita lihat penyelesaian sebuah loop yang lebih baik menggunakan rekursif daripada iterasi. Penyelesaian masalah dengan perulangan menggunakan iterasi secara tegas juga digunakan pada struktur kontrol pengulangan. Sementara itu, untuk rekursif, task diulangi dengan memanggil sebuah method perulangan.
Maksud dari hal tersebut adalah untuk menggambarkan sebuah masalah ke dalam lingkup yang lebih kecil dari perulangan itu sendiri. Pertimbangkan penghitungan faktorial dalam penentuan bilangan
bulat. Definisi rekursif dari hal tersebut dapat diuraikan sebagai berikut: factorial(n) = factorial(n-1) * n; factorial(1) = 1. Sebagai contohnya, nilai faktorial dari 2 sama dengan fatorial (1)*2, dimana hasilnya adalah 2. Faktorial dari 3 adalah 6, dimana sama dengan faktorial dari (2)*3.
Dengan iterasi, proses diakhiri ketika kondisi loop gagal atau salah. Dalam kasus dari penggunaan rekursif, proses yang berakhir dengan kondisi tertentu disebut permasalahan dasar yang telah tercukupi oleh suatu pembatasan kondisi. Permasalahan yang mendasar merupakan kejadian yang paling kecil dari sebuah masalah. Sebagai contoh, dapat dilihat pada kondisi rekursif pada faktorial, kasus yang mudah adalah ketika masukannya adalah 1. 1 dalam kasus ini merupakan dasar dari masalah. Penggunaan dari iterasi dan rekursif dapat bersama-sama memandu loops jika hal ini tidak digunakan dengan benar. Keuntungan iterasi dibandingkan rekursif adalah performance yang lebih baik. Hal tersebut lebih cepat untuk rekursif sejak terbentuknya sebuah parameter pada sebuah method yang menyebabkan adanya suatu CPU time. Bagaimanapun juga, rekursif mendorong pelatihan perancangan software yang lebih baik, sebab teknik ini biasanya dihasilkan dalam kode yang singkat yang lebih mudah untuk dimengerti dan juga mempromosikan reusability pada suatu solusi yang sebelumnya telah diterapkan. memilih antara iterasi dan rekursif merupakan permasalahan dari menjaga keseimbangan antara baiknya sebuah performance dan baiknya perancangan software.
Contoh Faktorial
Listing program berikut ini menunjukkan bagaimana menghitung faktorial menggunakan teknik iterasi.
class FactorialIter {
static int factorial(int n) {
int result = 1;
for (int i = n; i > 1; i--) {
result *= i;
}
return result;
}
public static void main(String args[]) {
int n = Integer.parseInt(args[0]);
System.out.println(factorial(n));
}
}
Dibawah ini merupakan listing program yang sama tetapi menggunakan rekursif.
class FactorialRecur {
static int factorial(int n) {
if (n == 1) { /* The base case */
return 1;
}
/* Recursive definition; Self-invocation */
return factorial(n-1)*n;
}
public static void main(String args[]) {
int n = Integer.parseInt(args[0]);
System.out.println(factorial(n));
}
}
Print n in any Base : Contoh yang lain
Sekarang, mempertimbangkan dari masalah dalam pencetakkan suatu angka desimal yang nilai basenya telah ditetapkan oleh pengguna. Ingat bahwa solusi dalam hal ini untuk menggunakan repetitive division dan untuk menulis sisa perhitungannya. Proses akan berakhir ketika sisa hasil pembagian kurang dari base yang ditetapkan. Dapat diasumsikan jika nilai input desimal adalah 10 dan kita akan mengkonversinya menjadi base 8. Inilah solusinya dengan perhitungan menggunakan pensil dan kertas.
Dari solusi diatas, 10 adalah sama dengan 12 base 8.
Contoh berikutnya. Nilai input desimalnya adalah 165 dan akan dikonversi ke base 16.
165 adalah sama dengan A5 base 16. Catatan: A=10.
Berikut ini merupakan solusi iterative untuk masalah diatas.
class DecToOthers {
public static void main(String args[]) {
int num = Integer.parseInt(args[0]);
int base = Integer.parseInt(args[1]);
printBase(num, base);
}
static void printBase(int num, int base) {
int rem = 1;
String digits = "0123456789abcdef";
String result = "";
/* langkah interasi */
while (num!=0) {
rem = num%base;
num = num/base;
result = result.concat(digits.charAt(rem)+"");
}
/* mencetak reverse dari result */
for(int i = result.length()-1; i >= 0; i--) {
System.out.print(result.charAt(i));
}
}
}
Berikut ini merupakan rekursif untuk masalah yang sama dengan solusi sebelumnya.
class DecToOthersRecur {
static void printBase(int num, int base) {
String digits = "0123456789abcdef";
/* Langkah Rekursif*/
if (num >= base) {
printBase(num/base, base);
}
/* Base case: num < base */
System.out.print(digits.charAt(num%base));
}
public static void main(String args[]) {
int num = Integer.parseInt(args[0]);
int base = Integer.parseInt(args[1]);
printBase(num, base);
}
}
Materi lengkapnya, Disini
Hay sahabat Blogger. Terima kasih sudah berkunjung di blog saya.. Semoga bermanfaat yah :)
0 komentar:
Posting Komentar