rekursif java
TRANSCRIPT
Struktur Data & Algoritma
Suryana Setiawan, Ruli Manurung & Ade Azurat
(acknowledgments: Denny)
1
Fasilkom UI
SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Rekursif
2SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Outline
Lanjutan ADT dan Java Collection API Menggunakan Java Collection API Mengimplementasi abstract method
Dasar-dasar Rekursif Apa itu recusion/rekursif? Aturan Rekursif Induksi Matematik
3SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Tujuan
Dapat menggunakan Java Collection API Memahami dasar-dasar rekursif
4SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Lanjutan Java Collection API
5SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Menggunakan Java Collection API
Kapan kita perlu menggunakan Java Collection API? Saat kita memerlukan ADT dan ADT tersebut
telah disediakan oleh Java Collection API Bagaimana cara menggunakan Java
Collection API?
6SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Menggunakan Java Collection API Cari Class yang merupakan implementasi
lengkap dari ADT yang kita butuhkan. Contoh: Kita membutuhkan ADT Stack. Java memiliki implementasi lengkap dari ADT
Stack pada: java.util.Stack
Buat Object baru dengan new java.util.Stack(), atau
Tuliskan di awal program: import java.util.Stack; atau: import java.util.*;
7SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Menggunakan Java Collection API
Bagaimana bila Java Collection API tidak miliki implementasi lengkap dari sebuah ADT tapi : hanya memiliki interface-nya saja atau implementasi yang tersedia tidak sesuai dengan
yang kita inginkan.
8SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Menggunakan Java Collection API
Kita harus mengidentifikasi interface-nya dan membuat kelas baru yang meng-implement seluruh method yang di sebutkan dalam interface tersebut. Untuk beberapa interface, Java Collection API
menyediakan abstract class yang dapat kita extends untuk meringankan beban kita sehingga tak perlu mengimplement seluruh method.
Contoh:
• Misalkan kita ingin membuat implementasi sederhana dari ADT set.
• Kita cukup mengextends abstract class AbstractSet dan melengkapi method-method-nya.
9SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: Menggunakan ADT Set
ADT Set adalah abstract data type yang tidak mengizinkan adanya duplikasi dalam koleksi data.
dalam Java Collection API, interface java.util.Set adalah representasi dari ADT set.
Dalam interface tersebut tidak terdapat implementasi, melainkan hanya nama-nama method yang merupakan interface untuk menggunakan ADT set.
10SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: Menggunakan ADT Set Interface Set tidak mendefinisikan method
baru dibanding parent interface Collection, Namun mengubah spesifikasi dari method:
boolean add(E e) boolean addAll(Collection<? extends E> c)
Kedua method tersebut hanya akan menambahkan data bila tidak ada duplikasi.
Return value: True, bila terjadi perubahan data (tidak ada duplikasi)
Return value: False, bila data sudah ada sebelumnya (penambahan dapat menimbulkan duplikasi)
11SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: Menggunakan ADT Set
Interface Set tidak menyediakan implementasi
Abstract Class AbstractSet hanya menyediakan implementasi dari tiga methods: boolean equals(Object o) int hashCode() boolean removeAll(Collection<?> c)
Class dengan implementasi lengkap antara lain adalah: HashSet, TreeSet, dan EnumSet.
12SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail:
Bagaimana duplikasi bisa dihindari dalam
ADT Set?
13SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail:
Duplikasi dideteksi dengan menggunakan method equals yang diturunkan dari kelas Object.
Elemen dari koleksi Set harus memiliki definisi equals yang masuk akal.
Seringkali sekedar menggunakan default implementasi tidak cukup dan tidak sesuai dengan yang kita inginkan.
Contoh Set<DataMhs>, elemen-nya adalah class DataMhs. Kita harus memiliki definisi equals yang tepat untuk
DataMhs, yaitu misalnya nama dan tanggal lahir harus unik. Definisi equals berdasarkan nama saja tidak cukup. Definisi equals mengikut sertakan hobby tidak relevan.
14SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail: HashSet
HashSet. Salah satu Implementasi interface Set Element perlu mendefinisian ulang (meng-
override) method hashCode(). Secara umum (average), operasi pada hashCode
adalah O(1). (Konstan).
15SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail: HashSet
Mengimplementasikan ulang method: equals dan hashCode.
harus meng-override bukan overload.(signature harus sama persis)
Bayangkan method hashCode dibutuhkan untuk memberikan 'petunjuk' kepada HashSet dimana meletakkan data dalam memory.
Lihat Studi kasus BasedClass dan DerivedClass (Weiss, p.233)
16SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail: HashSet
Hubungan antara equals dan hashCode jika, x.equals(y), maka kita harus menjamin
bahwa: x.hashCode = y.hashCode jika, ! x.equals(y), maka kita sepantasnya
menjamin bahwa x.hashCode ≠ y.hashCode
Bagaimana definisi equals yang baik? Bagaimana definisi hashCode yang baik? Kita akan mempelajari lebih dalam
mengenai hashCode dalam kuliah selanjutnya.
Untuk sementara ini, lihat contoh berikut:
17SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: equals dan hashCode (1)
Class StudentData{ String studentID, firstName, lastName, address;
public boolean equals(Object x){if (x == null || x.getClass() != getClass())
;return false{
{()public int hashCode;return Integer.parseInt(studentID)
{{
Class StudentData{ String studentID, firstName, lastName, address;
public boolean equals(Object x){if (x == null || x.getClass() != getClass())
return false;{
public int hashCode(){return Integer.parseInt(studentID);
{{
18SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: equals dan hashCode (2)
Class StudentData{ String studentID, firstName, lastName, address;
public boolean equals(Object x){return studentID.equals
(((StudentData)x).studentID);{
public int hashCode(){return firstName.length()
+ lastName.length() + address.length();
{{
Class StudentData{ String studentID, firstName, lastName, address;
public boolean equals(Object x){return studentID.equals
(((StudentData)x).studentID);{
public int hashCode(){return firstName.length()
+ lastName.length() + address.length();
{{
19SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: Menggunakan HashSet
Apa output berikut ini? java SetTester this is a very very very funny test
import java.util.HashSet;import java.util.Iterator;import java.util.Set;
public class SetTester{ public static void main(String[] args) { Set<String> mySet = new HashSet<String>(); for(int ii=0; ii<args.length; ii++) .mySetadd(args[ii]) ; ;()Iterator<String> myIterator = mySet.iterator while(myIterator.hasNext()) ;System.out.println(myIterator.next()) {{
import java.util.HashSet;import java.util.Iterator;import java.util.Set;
public class SetTester{ public static void main(String[] args) { Set<String> mySet = new HashSet<String>(); for(int ii=0; ii<args.length; ii++) mySet.add(args[ii]); Iterator<String> myIterator = mySet.iterator(); while(myIterator.hasNext()) System.out.println(myIterator.next()); {{
20SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail: SortedSet
Interface Set memiliki subinterface salah satunya: SortedSet.
Interface SortedSet, menjaga agar elemen dalam koleksi terurut.
Object Iterator akan menjamin elemen dalam SortedSet akan dibaca secara berurut.
21SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail: SortedSet Method tambahan dalam interface SortedSet, antara lain: E first()
Memberikan elemen pertama (terkecil) dalam set. E last()
Memberikan elemen terakhir (terbesar) dalam set. SortedSet<E> subSet(E x, E y)
Memberikan sub set antara x dan y. SortedSet<E> headSet(E x)
Memberikan bagian set yang elemennya lebih kecil (<) dari pada x.
SortedSet<E> tailSet(E x)Memberikan bagian set yang elemennya lebih besar (>) dari pada x.
22SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Bagaimana elemen dapat terurutdalam SortedSet?
23SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical Detail: Comparable
Elemen sebuah SortedSet haruslah mengimplement Interface Comparable.
Lebih detail lagi, harus mengimplement method: public int compareTo(E x)
Sebagaimana Set umumnya, duplikasi dideteksi dengan method equals.
Dua buah elemen e1 dan e2 dianggap sama bila: e1.compareTo(e2)==0
Maka definisi equals dan compareTo, harus konsisten!
24SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Technical detail: TreeSet
Salah satu implementasi dari SortedSet adalah kelas : TreeSet
Secara umum, rata-rata operasi pada TreeSet adalah O(log n), namun worst case adalah O(n).
25SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Contoh: TreeSetimport java.util.Iterator;import java.util.SortedSet;import java.util.TreeSet;
public class SortedSetTester{ public static void main(String[] args){ SortedSet<String> mySortedSet =
new TreeSet<String>(); for(int ii=0; ii<args.length; ii++) .mySortedSetadd(args[ii]); = Iterator<String> myIterator
;()mySortedSet.iterator while(myIterator.hasNext()) ;System.out.println(myIterator.next()) {{
import java.util.Iterator;import java.util.SortedSet;import java.util.TreeSet;
public class SortedSetTester{ public static void main(String[] args){ SortedSet<String> mySortedSet =
new TreeSet<String>(); for(int ii=0; ii<args.length; ii++) mySortedSet.add(args[ii]); Iterator<String> myIterator =
mySortedSet.iterator(); while(myIterator.hasNext()) System.out.println(myIterator.next()); {{
Apa output berikut ini? java SetTester this is a very very very funny test
26SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Dasar-dasar Rekursif
27SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Apa itu Rekursif?
Method yang memanggil dirinya sendiri baik secara langsung maupun secara tidak langsung. f(0) = 0; f(x) = 2 f(x-1) + x2
• f(1) = 1; f(2) = 6; f(3) = 21; f(4) = 58 fib(n) = fib(n - 1) + fib(n - 2)
public static int f (int x)
{
if (x == 0) return 0;
return 2 * f (x - 1) + x * x;
{
public static int f (int x)
{
if (x == 0) return 0;
return 2 * f (x - 1) + x * x;
{
28SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Method/Fungsi Recursion
Fungsi yang memanggil dirinya, secara langsung atau lewat fungsi lain, disebut fungsi rekursif
Proses pemanggilan diri itu disebut rekursi (recursion).
Contoh: Memangkatkan bilangan real tak nol dengan
suatu pangkat bilangan bulat
xn={ 1 jika n=0x∗xn−1 jika n01
x−n jika n0
29SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
/**
Menghitung pangkat sebuah bilangan real
(versi rekursif).
@param x bilangan yang dipangkatkan (x != 0)
@param n pangkatnya
*/
public static
double pangkatRekursif (double x, int n)
{
if (n == 0) {
return 1.0;
} else if (n > 0) {
return (x * pangkatRekursif (x, n - 1));
} else {
return (1 / pangkatRekursif (x, -n));
}
}
/**
Menghitung pangkat sebuah bilangan real
(versi rekursif).
@param x bilangan yang dipangkatkan (x != 0)
param n pangkatnya@
/*
public static double pangkatRekursif (double x, int n)
{
{ if (n == 0)
;return 1.0
{ else if (n > 0) {
;return (x * pangkatRekursif (x, n - 1))
{ else {
;return (1 / pangkatRekursif (x, -n))
{
{
/**
Menghitung pangkat sebuah bilangan real
(versi rekursif).
@param x bilangan yang dipangkatkan (x != 0)
@param n pangkatnya
*/
public static double pangkatRekursif (double x, int n)
{
if (n == 0) {
return 1.0;
{ else if (n > 0) {
return (x * pangkatRekursif (x, n - 1));
{ else {
return (1 / pangkatRekursif (x, -n));
{
{
30SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Berapa nilai pangkat 4-2?
pangkatRekursif (4.0, 2) return (4.0 * pangkatRekursif (4.0, 1));
pangkatRekursif (4.0, 1) return (4.0 * pangkatRekursif (4.0, 0));
pangkatRekursif (4.0, 0) return 1.0;
Recu
rsiv
e c
alls
1.0
4.0
16.0
0.0625
Retu
rnin
g v
alu
es
pangkatRekursif (4.0, -2) return (1 / pangkatRekursif (4.0, 2));
pangkatRekursif (4.0, 2) return (4.0 * pangkatRekursif (4.0, 1));
pangkatRekursif (4.0, 1) return (4.0 * pangkatRekursif (4.0, 0));
pangkatRekursif (4.0, 0) return 1.0;
Recu
rsiv
e c
alls
1.0
4.0
16.0
0.0625
Retu
rnin
g v
alu
es
pangkatRekursif (4.0, -2) return (1 / pangkatRekursif (4.0, 2));
31SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Algoritme Rekursif
Ciri masalah yang dapat diselesaikan secara rekursif adalah masalah itu dapat di-reduksi menjadi satu atau lebih masalah-masalah serupa yang lebih kecil
Secara umum, algoritme rekursif selalu mengandung dua macam kasus: kasus induksi: satu atau lebih kasus yang
pemecahan masalahnya dilakukan dengan menyelesaikan masalah serupa yang lebih sederhana (yaitu menggunakan recursive calls)
kasus dasar atau kasus penyetop (base case): satu atau lebih kasus yang sudah sederhana sehingga pemecahan masalahnya tidak perlu lagi menggunakan recursive-calls.
Supaya tidak terjadi rekursi yang tak berhingga, setiap langkah rekursif haruslah mengarah ke kasus penyetop (base case).
32SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Aturan Rekursif1.Punya kasus dasar
Kasus yang sangat sederhana yang dapat memproses input tanpa perlu melakukan rekursif (memanggil method) lagi
2.Rekursif mengarah ke kasus dasar3.Percaya.
Pada proses pemanggilan rekursif, asumsikan bahwa pemanggilan rekursif (untuk problem yang lebih kecil) adalah benar. Contoh: pangkatRekursif (x, n)
• Asumsikan: pangkatRekursif (x, n - 1) menghasilkan nilai yang benar.
• Nilai tersebut harus diapakan sehingga menghasilkan nilai pangkatRekursif (x, n) yang benar?
• Jawabannya: dikalikan dengan x4.Aturan penggabungan: Hindari duplikasi
pemanggilan rekursif untuk sub-problem yang sama.
33SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Infinite Recursion
public static int bad (int n)
{
if (n == 0) return 0;
return bad (n * 3 - 1) + n - 1;
{
public static int bad (int n)
{
if (n == 0) return 0;
return bad (n * 3 - 1) + n - 1;
{
34SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
How it works?
Java VM menggunakan internal stack of activation records
Activation record dapat dilihat sebagai kertas yang berisi informasi tentang method nilai parameter variabel lokal program counter (PC)
35SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
How it works? Ketika suatu method G dipanggil, sebuah
activation record untuk G dibuat dan di-push ke dalam stack; saat ini G adalah method yang sedang aktif
Ketika method G selesai (return), stack di-pop; method dibawah G yang dipanggil.
36SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Too Much Recursion
Di sebuah system, n >= 9410 tidak dapat dieksekusi
public static long s (int n){ if (n == 1) { return 1; { else { return s (n - 1) + n; {{
public static long s (int n){ if (n == 1) { return 1; { else { return s (n - 1) + n; {{
37SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Pembuktian dgn Induksi
Contoh kasus: pangkatRekursif (x,n) Buktikan bahwa base case benar.
pangkatRekursif (x,0) = 1 Buktikan bahwa inductive case benar
Perhitungan/proses untuk input yang lebih kecil dapat diasumsikan memberikan jawaban yang benar atau melakukan proses dengan benar.• asumsikan bahwa pangkatRekursif (x, n-1) memberikan nilai xn-1
apakah pangkatRekursif (x, n) mengembalikan nilai yang benar?•pangkatRekursif (x, n) = pangkatRekursif (x, n-1) * x
• xn = xn-1 * x
38SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Bilangan Fibonacci
F0 = 0, F1 = 1, FN = FN-1 + FN-2 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
public static int fib1 (int n)
{
;if (n <= 1) return n
;return fib1 (n – 1) + fib1 (n – 2)
{
public static int fib1 (int n)
{
if (n <= 1) return n;
return fib1 (n – 1) + fib1 (n – 2);
{
39SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Bilangan Fibonacci
Untuk N = 40, FN melakukan lebih dari 300 juta pemanggilan rekursif. F40 = 102.334.155 Analisa algoritme, Growth rate: exponential!!!
Aturan: Jangan membiarkan ada duplikasi proses yang mengerjakan input yang sama pada pemanggilan rekursif yang berbeda. (Aturan ke-4)
Ide: simpan nilai fibonacci yang sudah dihitung dalam sebuah array
40SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Bilangan Fibonacci
Dynamic Programming menyelesaikan sub-permasalahan dengan menyimpan hasil sebelumnya. public static int fib2 (int n){
if (n <= 1) return n; int result[] = new int[n + 1]; result[0] = 0; result[1] = 1; for (int ii = 2; ii <= n; ii++) { result[ii] = result[ii - 2] + result[ii - 1]; { return result[n];{
public static int fib2 (int n){ if (n <= 1) return n; int result[] = new int[n + 1]; result[0] = 0; result[1] = 1; for (int ii = 2; ii <= n; ii++) { result[ii] = result[ii - 2] + result[ii - 1]; { return result[n];{
41SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Bilangan Fibonacci
public static int fib3 (int n){ if (n <= 1) return n;
int fib1 = 0; int fib2 = 1; int result; for (int ii = 2; ii <= n; ii++) { result = fib2 + fib1; fib1 = fib2; fib2 = result; { return result;{
public static int fib3 (int n){ if (n <= 1) return n;
int fib1 = 0; int fib2 = 1; int result; for (int ii = 2; ii <= n; ii++) { result = fib2 + fib1; fib1 = fib2; fib2 = result; { return result;{
Hanya menyimpan dua hasil sebelumnya saja.
42SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Bilangan Fibonacci
Implementasi rekursif yang lebih efficient. Pendekatan Tail Recursive.
public static long fib4 (int n){return fiboHelp(0,1,n);
{
static long fiboHelp(long x, long y, int n){
if (n==0) return x;else if (n==1) return y;else return fiboHelp(y, x+y, n-1);
{
public static long fib4 (int n){return fiboHelp(0,1,n);
{
static long fiboHelp(long x, long y, int n){
if (n==0) return x;else if (n==1) return y;else return fiboHelp(y, x+y, n-1);
{
43SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Kesalahan Umum
Base case terlalu kompleks Progress tidak menuju base case Duplikasi proses untuk nilai input yang
sama dalam recursive call yang terpisah. Tidak efisien.
44SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
Ringkasan
Method rekursif adalah method yang memanggil dirinya sendiri baik secara langsung maupun secara tidak langsung.
Aturan Rekursif Definisikan base case: yang dapat memproses
input tanpa perlu recursive lagi Pada bagian rekursif pastikan akan bergerak
menuju base case. Asumsikan bahwa pemanggilan rekursif
terhadap sub problem berjalan benar. hindari duplikasi proses untuk nilai input yang
sama dalam recursive call yang terpisah. Bila memungkinkan lakukan tail recursive.
45SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P
Semester Ganjil – 2008/2009
What’s Next
Lanjutan Rekursif Devide and Conquer Backtracking Latihan Rekursif