Hari: 5 April 2012

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.