Bulan: April 2012

Struktur Data 11

MENARA HANOI

Permainan ini adalah contoh klasik dari proses rekursif. 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 lainnya dan diperbolehkan melewati tonggak bantuan.
Aturannya?
Aturan permainan menara Hanoi
Semua piringan pada tonggak A akan dipindahkan ke tonggak C dengan ketentuan bahwa pemindahan piringan dilakukan satu per-satu dan piringan yang lebih besar tidak boleh diletakkan di atas piringan yang lebih kecil.
Menurut legenda dikatakan bahwa jika anda selesai memindahkan seluruh 64 piringan, pada saat itu juga dunia kiamat. Bayangkan jika untuk setiap pemindahan perlu satu detik.

Struktur Data 10

Proses rekursi di program p_318b

Mempunyai kondisi pengakhiran rekursi yaitu jika nilai n sudah lebih kecil atau sama dengan nol. Setiap kali fungsi memanggil dirinya sendiri, nilai dari n dikurangi dengan nilai satu, sehingga nilai n akhirnya akan menjadi nol dan proses rekursi akan diakhiri, sehingga fungsi ini akan memanggil dirinya sendiri sebanyak n kali.
Program di p_319 merupakan program menghitung n! Yang akan dikerjakan secara rekursi.
Program di p_322 merupakan
Program untuk mengurutkan data dengan metode quick sort yang dilakukan secara rekursi. Metode ini menggunakan teknik memecah data menjadi partisi-partisi sehingga metode ini disebut dengan nama metode pengurutan pertukaran partisi (partition exchange sort).
Proses pengurutan dimulai dengan memilih sebuah elemen secara sembarang. Di program, elemen yang dipilih adalah elemen terbawah.

	


	





	

		
		
Struktur Data 9
	


	
	
	

		
Kamis 22 Maret 2012


Buku referensi: Jogiyanto Hartono, MBA, PhD, 1993. Konsep Dasar Pemrograman Bahasa C, Penerbit Andi, Yogyakarta.
Materi: Bab 9 Larik, Bab 10 Pointer, Bab 11 Fungsi, Bab 12 Tipe Data Tingkat Lanjut.
Bab 11, bagian 11.11. Rekursi, hlm 318. Rekursi (recursion) adalah suatu proses dari fungsi yang memanggil dirinya sendiri secara berulang-ulang.


Karena proses dilakukan


Berulang-ulang, harus ada suatu kondisi yang mengakhiri prosesnya. Jika tidak, maka proses tidak akan pernah berhenti sampai memori yang digunakan tidak dapat menampung lagi.
Program contoh di p_318 merupakan program rekursi yang tidak akan berhenti karena tidak mempunyai kondisi yang menghentikan prosesnya. Proses rekursi ini ditunjukkan oleh statemen terus_tidak_berhenti() yaitu proses yang memanggil fungsi dirinya sendiri.



	


	





	

		
		
Struktur Data 8
	


	
	
	

		
Hubungan rekurens sbb


•FIBO(N) = FIBO (N-1) + FIBO (N-2)


•Karena FIBO(N) ditentukan oleh 2 nilai yang berbeda dengan argumen yang nilainya lebih kecil, untuk mencari bilangan Fibonnaci diperlukan 2 nilai awal yaitu


•FIBO(1) = 1


•FIBO(2) = 2


PR




•Buat program untuk mencari bilangan Fibonnaci. Boleh memakai bahasa C++, Pascal, Basic, dll.


•Dikumpulkan kamis depan dalam bentuk makalah di mana ada pengantar, source code, hasil running program, pembahasan, simpulan.


•Source sudah dimodifikasi di mana ada identitas dan keterangan program.



	


	





	

		
		
Struktur Data 7
	


	
	
	

		
Notasi pemrograman


•FAKTORIAL(0) = 1  1)


•FAKTORIAL(N) = N x FAKTORIAL(N-1)  2)


•


•Persamaan 2) di atas merupakan contoh hubungan rekurens (recurrence relation), 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. Setiap fungsi rekursi paling sedikit mempunyai satu nilai awal. Jika tidak, fungsi tersebut tidak bisa dihitung secara eksplisit.




Bilangan Fibonnaci




•Bisa didefinisikan berdasarkan deret integer tak berhingga sebagai berikut:


•1, 1, 2, 3, 5, 8, 12, 13, 21, 34, 55, 89, …


•Bilangan ke-N, di mana (N > 2) dalam deret bisa dicari dari dua bilangan sebelumnya yang terdekat dengan bilangan ke-N yaitu bilangan ke-(N-1) dan bilangan ke-(N-2).


•Jika FIBO (N) menunjukkan bilangan Fibonnaci ke-N maka FIBO (N) bisa dihitung berdasarkan



	


	





	

		
		
Struktur Data 6
	


	
	
	

		
Hati-hati


•Dalam prosedur atau fungsi, pemanggilan ke diri sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.


•Dalam pemakaian sehari-hari, rekursi merupakan teknik pemrograman pada pekerjaan dengan mengekspresikannya ke dalam suku-suku dari program lain dengan menambah langkah-langkah sejenis.


Contoh




•Menghitung nilai faktorial dari bilangan bulat positif dan mencari deret Fibonnaci dari suatu bilangan bulat.


•Faktorial, nilainya secara rekursif dapat ditulis sebagai


•0! = 1,


•N! = N x (N – 1)! untuk N > 0



	


	





	

		
		
Struktur Data 5
	


	
	
	

		
•Dosen: RASP, MK


•Jadwal: Kamis 13.30 – 15.00 wib.


•Penilaian: PR, KLP, UTS.


•Materi: Berbahasa C++ dan Pascal terdiri atas 1) Rekursi, 2) Tumpukan, 3) Tipe data pointer, 4) Senarai berantai, 5) Antrian, 6) Senarai berantai banyak, 7) Pohon, 8) Pengurutan, 9) Pencarian, 10) Program terapan, 11) Graph, 12) Pengelolaan pengingat.




•Program = struktur data + algoritma


REKURSI




•Pengertian: rekursi berarti suatu proses yang bisa memanggil dirinya sendiri.


•Dalam rekursi sebenarnya terkandung pengertian prosedur atau fungsi.


•Perbedaannya adalah rekursi bisa memanggil diri sendiri, prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi.