SATUAN ACARA PERKULIAHAN (SAP) Mata Kuliah Kode Semester Waktu Pertemuan
: Struktur Data : TIS3213 : III : 1 x 3 x 50 Menit :3
A. Kompetensi 1. Utama Mahasiswa dapat memahami tentang konsep pemrograman menggunakan struktur rekursi.
2. Pendukung Mahasiswa dapat mengetahui contoh-contoh proses rekursif.
B. Pokok Bahasan Rekursi
C. Sub Pokok Bahasan o Pengertian Rekursi o Proses Rekursif o Menyusun Permutasi o Menara Hanoi
D. Kegiatan Belajar Mengajar Tahapan Kegiatan Pendahuluan
Kegiatan Pengajaran
1. 2.
Penyajian
1. 2.
Kegiatan Mahasiswa Menjelaskan perkuliahan yang Mendengarkan dan akan dijalani dalam satu semester memberikan Menjelaskan materi-materi komentar perkuliahan dan buku-buku acuan yang akan dipergunakan dalam semester ini Memperhatikan, Menjelaskan tentang pengertian mencatat, dan rekursi memberikan Menjelaskan tentang proses
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
Media & Alat Peraga Notebook, LCD, Papan Tulis
Notebook, LCD, Papan Tulis
19
3. 4. Penutup
1. 2. 3.
rekursif Menjelaskan tentang cara menyusun permutasi Menjelaskan tentang menara hanoi Mengajukan pertanyaan kepada mahasiswa. Memberikan kesimpulan. Mengingatkan akan kewajiban untuk pertemuan selanjutnya.
komentar. Mengajukan pertanyaan.
Memberikan komentar. Mengajukan menjawab pertanyaan
Notebook, LCD, Papan dan Tulis
E. Evaluasi Evaluasi dilakukan dengan cara memberikan pertanyaan langsung dan tidak langsung kepada mahasiswa.
F. Daftar Referensi 1. P. Insap Santosa, Struktur Data Menggunakan Turbo Pascal 6.0, Andi Offset, Yogyakarta, 2001 2. Wirth Niklaus, “Algorithms and Data Structure”, Prentice Hall Int. Inc, 1986 3. Antonie Pranata, Algoritma dan Pemrograman, J&J Learning Yogyakarta, 2000 4. Dwi Sanjaya, Bertualang dengan Struktur Data di Planet Pascal, J&J Learning Yogyakarta, 2001 5. Materi – Materi dari Internet.
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
20
RENCANA KEGIATAN BELAJAR MINGGUAN (RKBM) Mata Kuliah Kode Semester Waktu Pertemuan
Minggu Ke1
3
Topik (Pokok Bahasan) 2 2.1 Pengertian Rekursi 2.2 Proses Rekursif 2.3 Menyusun Permutasi 2.4 Menara Hanoi
: Struktur Data : TIS3213 : III : 1 x 3 x 50 Menit :3
Estimasi Waktu (Menit) 4
Metode Pembelajaran 3 Ceramah, Diskusi Kelas
1 x 3 x 50’
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
Media 5 Notebook, LCD, Papan Tulis
21
BAB II
REKURSI 2.1 PENGERTIAN REKURSI Rekursi berarti suatu proses yang bisa memanggil dirinya sendiri. Dalam rekursi terkandung pengertian prosedur atau fungsi. Perbedaannya adalah rekursi bisa memanggil ke dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi. Contoh paling sederhana dari proses rekursi adalah proses menghitung nilai faktorial dari bilangan bulat positif. Nilai faktorial, secara rekursif dapat ditulis sebagai : 0!=1 N ! = N x (N – 1) !
untuk N > 0
yang secara notasi pemrograman bisa ditulis sebagai : FAKTORIAL (0) = 1
(1)
FAKTORIAL (N) = N * FAKTORIAL (N – 1)
(2)
Persamaan (1) disebut nilai awal. Persamaan (2) merupakan contoh hubungan rekurens (recurrence relation), dimana nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil. Contoh lain dari proses rekursi adalah mencari deret fibonacci dari suatu bilangan bulat. Bilangan fibonacci bisa didefinisikan berdasar deret integer tak berhingga berikut : 1
1
2
3
5
8
13
21
34
55
...
Dari deret diatas bisa dilihat bahwa bilangan ke N (N > 2) dalam deret bisa dicari dari 2 (dua) bilangan sebelumnya, yaitu bilangan ke (N – 1) dan bilangan ke (N – 2). Sehingga, jika FIBO (N) menunjukkan bilangan fibonacci ke N, maka FIBO (N) bisa dihitung berdasar hubungan rekurens : FIBO (N) = FIBO (N – 1) + FIBO (N – 2) Untuk mencari bilangan fibonacci juga diperlukan dua nilai awal, yaitu : FIBO (1) = 1 dan FIBO (2) = 1
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
22
2.2 PROSES REKURSIF Untuk memahami proses rekursif yang terjadi dalam sebuah fungsi rekursi, perhatikan contoh dibawah ini : function FAKT (N : integer) : integer; begin if N = 0 then FAKT := 1 else FAKT := N * FAKT (N – 1) end; Program 2.1 Faktorial dengan cara rekursif
Dari fungsi diatas bisa dilihat bahwa FAKT (N) bisa dihitung dari FAKT (N – 1), dimana FAKT (N – 1) bisa dihitung dari FAKT (N – 2) dan seterusnya. Dengan demikian, fungsi diatas untuk N = 6 bisa kita lacak cara kerjanya, seperti terlihat pada Gambar 2.1. 4
24 FAKT
3
6 FAKT
2
2 FAKT
1
1 FAKT
0
1 FAKT
Gambar 2.1 Ilustrasi fungsi FAKT
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
23
Gambar 2.1 bisa dijelaskan sebagai berikut (panah kebawah menunjukkan nilai parameter aktual yang dilewatkan kedalam fungsi FAKT). Pada saat program mengerjakan FAKT (4) ia akan mentest bahwa 4 tidak sama dengan 0 (karena FAKT (0) ditetapkan sebagai nilai awal). Dengan demikian perlu menghitung FAKT (N – 1) (yang sama dengan FAKT (3)) terlebih dahulu, sehingga program akan mengerjakan FAKT (3), sementara bilangan 4 dan operatornya akan disimpan lebih dahulu. Dalam hal ini program juga menjumpai bahwa 3 tidak sama dengan 0. Proses diteruskan sampai program mengeksekusi FAKT (0), maka proses rekursif dihentikan. Dengan telah diperolehnya nilai FAKT (0), maka segera bisa diperoleh nilai FAKT (1) yang sama dengan 1 * FAKT (0), hasilnya 1 (lihat panah keatas). Proses diteruskan sampai diperoleh nilai terakhir yang dikembalikan oleh fungsi FAKT ini, yaitu 24. Dengan cara yang sama, bisa dilacak proses yang terjadi pada saat program mengeksekusi fungsi FIBO untuk nilai N tertentu. Fungsi FIBO dapat dapat diimplementasikan seperti tersaji dalam Program 2.2 berikut ini : function FIBO (N : integer) : integer; begin if (N = 1) or (N = 2) then FIBO := 1 else FIBO := FIBO (N – 1) + FIBO (N – 2) end; Program 2.2 Deret Fibonacci dengan cara rekursif
2.3 MENYUSUN PERMUTASI Contoh lain dari proses rekursif adalah untuk menyusun semua permutasi yang mungkin dari sekelompok karakter. Sebagai contoh, jika kita mempunyai 3 buah karakter A, B, C, maka permutasi yang mungkin dari ketiga karakter ini adalah : A B C
B A C
C A B
A C B
B C A
C B A
Secara umum, banyaknya permutasi dari N buah karakter adalah N faktorial. Dalam contoh diatas N = 3, sehingga banyaknya permutasi adalah 3 ! = 6.
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
24
Proses penyusunan permutasinya bisa dijelaskan sebagai berikut : •
Cetak elemen ke 1, dan cetak permutasi elemen ke 2 sampai N ( permutasi dengan N – 1 elemen)
•
Cetak elemen ke 2, dan cetak permutasi elemen ke 1, elemen ke 3 sampai N ( permutasi dengan N – 1 elemen)
•
Cetak elemen ke 3, dan cetak permutasi elemen ke 1, elemen ke 2, elemen ke 4 sampai N ( permutasi dengan N – 1 elemen)
•
dan seterusnya, sampai langkah terakhir adalah cetak elemen ke N, dan cetak permutasi elemen ke 1 sampai elemen ke (N – 1) ( permutasi dengan N – 1 elemen)
Proses diulang terus sampai dicetak permutasi dengan 1 elemen. Sebagai contoh, untuk N = 3, maka caranya adalah : •
Cetak ’A’, dan cetak permutasi (’B’ ’C’);
•
Cetak ’B’, dan cetak permutasi (’A’ ’C’);
•
Cetak ’C’, dan cetak permutasi (’A’ ’B’);
2.4 MENARA HANOI Contoh klasik dari proses rekursif adalah permainan Menara Hanoi, berdasarkan legenda pertama kali dimainkan secara manual oleh seorang pendeta Budha di Hanoi. Dalam permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satu tonggak ke tonggak lain, dan diperbolehkan melewati tonggak bantuan. Aturan permainannya adalah sebagai berikut. Semua piringan pada tonggak A akan dipindah pada tonggak C dengan ketentuan bahwa pemindahan piringan dilakukan satu persatu dan piringan yang lebih besar tidak boleh diletakkan diatas piringan yang lebih kecil. Untuk lebih jelasnya lihat Gambar 2.2 dibawah ini.
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
25
Tonggak asal (A)
Tonggak bantu (B)
Tonggak tujuan (C)
Gambar 2.2 Ilustrasi permainan Menara Hanoi Secara sederhana, pemindahan seluruh piringan secara rekursif dapat dilaksanakan dengan : 1. Pindahkan (N – 1) piringan yang paling atas dari tonggak asal (A) ke tonggak bantu (B). 2. Pindahkan piringan ke N (piringan terakhir) dari tonggak asal (A) ke tonggak tujuan (C). 3. Pindahkan (N – 1) piringan dari tonggak bantu (B) ke tonggak tujuan (C).
Tetapi tentu saja piringan sebanyak (N – 1) buah tidak boleh dipindah bersamasama, tetapi harus satu per satu. Untuk mempermudah penyelesaian persoalan kita coba membuat satu notasi baru, misalnya : MENARA (N, Asal, Bantu, Tujuan)
Notasi diatas bisa dibaca “Pindahkan N buah piringan dari tonggak Asal ke tonggak Tujuan menggunakan tonggak Bantu”. Jika N = 1, maka notasi diatas bisa ditulis sebagai : MENARA (1, Asal, Bantu, Tujuan) yang secara langsung bisa kita laksanakan dengan memindahkan piringan dari tempat Asal ke tempat Tujuan. Untuk N > 1, penyelesaiannya bisa kita pecah menjadi 3 penyelesaian seperti diatas, yaitu : MENARA (N – 1, Asal, Tujuan, Bantu); MENARA (N, Asal, Bantu, Tujuan); atau Asal Æ Tujuan MENARA (N – 1, Bantu, Asal, Tujuan);
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
26
Contoh : Menara Hanoi dengan 4 buah piringan. MENARA (4, A, B, C) yang setelah dihitung perlu 15 kali perpindahan, yaitu : AÆB
AÆC
BÆC
AÆB
CÆA
CÆB
AÆB
AÆC
BÆC
BÆA
CÆA
BÆC
AÆB
AÆC
BÆC
--ooOOOoo--
Soal & Pembahasan :
Soal : 1. Apakah yang dimaksud dengan rekursi. 2. Sebutkan contoh-contoh proses rekursif.
Pembahasan : 1. Rekursi berarti suatu proses yang bisa memanggil dirinya sendiri. 2. Contoh proses rekursi : •
Menghitung nilai faktorial dari bilangan bulat positif. Nilai faktorial, secara rekursif dapat ditulis sebagai : 0!=1 N ! = N x (N – 1) !
•
untuk N > 0
Mencari deret fibonacci dari suatu bilangan bulat. FIBO (N) = FIBO (N – 1) + FIBO (N – 2) FIBO (1) = 1 dan FIBO (2) = 1
Struktur Data / Eva Yulianti, S.Kom.,M.Cs
27
