MATEMATIKA DISKRIT FUNGSI REKURSIF
OLEH: KELOMPOK 5 KETUA
: NINING SURYATI
ANGGOTA : NIKEN
(F1A117032) (F1A117010)
SARFIN
(F1A117040)
FITRIANI
(F1A117047)
NUR ALAM AKBAR (F1A117033) DARMAYANTO
(F1A116083)
PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS HALU OLEO KENDARI
2018 KATA PENGANTAR
Assalamu’alaikumwarahmatulahiwabarakatuh Pujisyukurkehadirat Allah SWT yang telah melimpahkan Hidayah, Inayah dan Rahmat-Nya serta memberikan kesehatan jasmani dan rohani sehingga kita masih bias menyelesaikan makalah Matematika Diskrit
yang berjudul Fungsi
Rekursif. Sholawat serta salam kita haturkan kepada teladan kita semua Nabi Muhammad SAW, yang telah memberitahu kepada kita jalan yang benar berupa ajaran agama yang sempurna serta menjadi rahmat bagi seluruh alam. Kami juga tidak lupa untuk mengucapkan terima kasih kepada Dosen mata kuliah Matematika Diskrit yang selalu mengajar dan membimbing kami. Harapan kami semoga makalah ini dapat menambah pengetahuan bagi para pembaca, Untuk kedepannya dapat memperbaiki bentuk maupun menambah isi makalah agar menjadi lebih baik lagi. Karena keterbatasan pengetahuan maupun pengalaman kami, kami yakin masih banyak kekurangan dalam makalah ini, Oleh karena itu kami sangat mengharapkan saran dan kritik yang membangun dari pembaca demi kesempurnaan makalah ini. Wa’alaikumsalamwarahmatulahiwabarakatuh
Kendari, 16 Oktober 2018
Penyusun
ii
DAFTAR ISI HALAMAN JUDUL ……………………………………….............................
i
KATA PENGANTAR ……………………………...…………………............
ii
DAFTAR ISI ………………………...………………………………...............
iii
BAB I PENDAHULUAN 1.1. LatarBelakang ……………………...……..……………………....
1
1.2. Rumusan Masalah ……………………………...……………….....
2
1.3. Tujuan………………..…………………………...……………....
2
BAB II PEMBAHASAN 2.1. Pengertian Fungsi Rekursif……………..…………………………..
3
2.2. Basis dan Rekurens…………………...……….……………….....
4
BAB III PENUTUP 3.1. Kesimpulan …………………..……………..……………………..
8
3.2. Saran ……………………………..………………………………...
8
DAFTAR PUSTAKA…………………..……………………………………..
iii
9
BAB I PENDAHULUAN 1.1 Latar Belakang Seiring dengan kebutuhan masyarakat yang dipengaruhi oleh perkembangan teknologi yang begitu pesat terutama di bidang komputer, hampir semua pengolahan data maupun transaksi diberbagai perusahaan diproses menggunakan komputer baik perusahaan swasta maupun instansi pemerintah. Penerapan sistem operasi telah berubah dari sistem manual menjadi sistem komputerisasi, hal itu cukup beralasan mengingat banyaknya kelebihan dari sistem komputerisasi antara lain adalah proses pembelajaran struktur data yang membahas tentang Rekursif dan Iteratif dalam Algoritma. Rekursif adalah proses pengulangan sesuatu dengan cara kesamaan-diri. Sebagai contohnya, saat dua cermin berada paralel antara satu dengan yang lain, gambar yang tertangkap adalah suatu bentuk rekursif tak-terbatas. Istilah ini memiliki makna beragam bergantung kepada ragam disiplin mulai dari linguistik sampai logika. Penggunaan paling umum dari rekursif yaitu dalam matematika dan ilmu komputer, yang mengacu kepada suatu metode mendefinisikan fungsi yang mana fungsi tersebut menggunakan definisinya sendiri. Secara spesifik hal ini mendefinisikan suatu instansi tak-terbatas (nilai fungsi), menggunakan ekpresi terbatas dengan beberapa instansi bisa merujuk ke instansi lainnya, tetapi dengan suatu cara sehingga tidak ada perulangan atau keterkaitan tak-terbatas dapat terjadi. Istilah ini juga digunakan secara umum untuk menjelaskan suatu proses pengulangan objek dengan cara kesamaan-diri. Komputer adalah sistem elektronik untuk memanipulasi data yang cepat dan tepat serta dirancang dan diorganisasikan supaya secara otomatis menerima dan menyimpan data input memperoses dan menghasilkan output dibawah pengawasan instruksi-instruksi program yang tersimpan di memori. 1.2 Rumusan Masalah Adapun rumusan masalah dalam makalah ini adalah sebagai berikut: 1.
Apa itu fungsi rekursif?
2.
Apa itu basis dan rekurens?
1.3 Tujuan Adapun tujuan dalam makalah ini adalah sebagai berikut: 1.
Mengetahui apa itu fungsi rekursif?
2.
Mengetahui apa itu basis dan rekurens? 1
BAB II PEMBAHASAN
2.1. Pengertian Fungsi Rekursif Rekursif berarti suatu proses yang memanggil dirinya sendiri. Dalam rekursif sebenarnya terkandung pengertian prosedur atau fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi. Rekursif merupakan teknik pemrograman yang penting, dan beberapa bahasa pemrograman modern mendukung keberadaan proses rekursif ini. Pemanggilan prosedur atau fungsi ke dirinya sendiri bisa berarti proses yang berulang yang tidak bisa diketahui kapan akan berakhir. Dalam pemakaian sehari-hari, rekursi merupakan teknik pemrograman yang berdaya guna untuk digunakan pada pekerjaan pemrograman dengan mengeksperisikannya ke dalam suku-suku dari program lain dengan menambahkan langkahlangkah sejenis. Contoh paling sederhana dari proses rekursif adalah menghitung nilai faktorial dari bilangan bulat. Tinjau kembali fungsi untuk menghitung faktorial dari bilangan bulat tak-negatif n yang didefinisikan sebagai berikut. n! = Sebagai contoh: 0! = 1 1! = 1 2! = 1 x 2 3! = 1 x 2 x 3 4! = 1 x 2 x 3 x 4
Sekarang coba perhatikan bahwa faktorial dari n dapat didefinisikan dalamterminologi faktorial juga:
2
0! = 1 1! = 1 x 0! 2! = 2 x 1! 3! = 3 x 2! 4! = 4 x 31 Nyatakanlah, bahwa untuk n > 0 kita melihat bahwa: n! = 1 x 2 x .... x (n - 1)! x n Dengan menggunakan notasi matematika, maka n! Didefinisikan dalam hubungan rekursif sebagai berikut: n! = Jika kita misalkan f(n) = n!, maka fungsi faktorial diatas dapat juga ditulis sebagai: f(n) = kita dapat melihat bahwa dalam proses perhitungan faktorial billangan tak-negatif n terdapat definisi faktorial itu sendiri. Cara pendefinisian seperti itu, yang mendefinisikan sebuah objek dalam terminologi dirinya sendiri dinamakan definisi Rekursif. Definisi 3.15 Fungsi f dikatakan fungsi rekursif jika definisi fungsinya mengacu pada dirinya sendiri. Nama lain dari fungsi rekursif adalah relasi rekurens (recurrence relation) bahwa fungsi adalah bentuk khusus relasi.
2.2. Basis dan Rekurens Fungsi rekursif disusun oleh dua bagian : a.
Basis
3
Bagian yang berisi nilai awal yang tidak mengacu pada dirinya sendiri. Bagian ini juga sekaligus menghentikan definisi rekursif (dan memberikan sebuah nilai yang terdefinisi pada fungsi rekursif). b.
Rekurens Bagian ini mendefinisikan argumen fungsi dalam terminilogi dirinya sendiri. Setiap kali
fungsi mengacu pada dirinya sendiri, argumen dari fungsi harus lebih dekat ke nilai awal (basis).
Tinjau kembali perhitungan n! Secara rekursif. Dengan mengingat kembali definisi rekursif dari faktorial. a) Basis n! = 1
, jika n = 0
b) Rekurens n! = n x (n – 1)!
, jika n > 0
Maka 5! Dihitung dengan langkah berikut: (1)
5! = 5 x 4!
(2)
(rekurens)
4! = 4 x 3!
(3)
3! = 3 x 2!
(4)
2! = 2 x 1!
(5)
1! = 1 x 0!
(6)
0! = 1
Pada baris (6) kita memperoleh nilai yang terdefinisi secara langsung dan bukan faktorial dari bilangan lainnya. Dengan melakukan ranut-balik (backtrack) dari baris (6) ke baris (1), kita mendapatkan nilai pada setiap baris untuk menghitung hasil pada baris sebelumnya: (6)
0! = 1
(5)
1! = 1 x 0! = 1 x 1 = 1
(4)
2! = 2 x 1! = 2 x 1 = 2 4
(3)
3! = 3 x 2! = 3 x 2 = 6
(2)
4! = 4 x 3! = 4 x 3 = 12
(1)
5! = 5 x 4! = 5 x 4 = 20
Jadi, 5! = 120
Contoh Dibawah ini adalah contoh-contoh fungsi rekursif lainnya. 1.
f(x) =
2.
Fungsi (polinom) Chebysev dinyatakan sebagai berikut:
3.
Barisan Fibonacci Dapat dinyatakan secara rekursif sebagai berikut:
Contoh Soal 1 Misalkan f didefinsikan secara rekusif sebagai berikut:
Tentukan nilai f(4) dari fungsi tersebut!
5
Jawaban:
Cara Lain Menghitungnya: f(0) = 3 f(1) = 2f(0) + 4 = 2 3 + 4 = 10 f(2) = 2f(1) + 4 = 2 10 + 4 = 24 f(3) = 2f(2) + 4 = 2 24 + 4 = 52 f(4) = 2f(3) + 4 = 2 52 + 4 = 108
Jadi, f(4) = 108.
Contoh Soal 2 1.
Definisikan an secara rekursif , yang dalam hal ini a adalah bilangan riil tidak-nol dan n adalah bilangan bulat tidak-negatif.
2.
Nyatakan a x b secara rekursif, yang dalam hal ini a dan b adalah bilangan bulat positif.
Jawaban:
6
BAB 3 PENUTUP 3.1. Kesimpulan Fungsi rekursif merupakan salah satu konsep yang penting untuk dikuasai. Hal ini dikarenakan fungsi ini memiliki sangat banyak implementasi, yang dalam hal ini adalah implementasi dalam algoritma. Fungsi rekursif dan fungsi iteratif memiliki kelebihan dan 7
kelemahan masing-masing. Secara umum fungsi rekursif memiliki algoritma yang lebih mudah dipahami dan dibuat tetapi membutuhkan penggunaan memoriyang besar. Rekursif dan interaktif mudah dan sederhana namun dapat memberikan manfaat yang besar bagi pembelajaran bahasa. Rekursif dan inreraktif ini dapat menampilkan teks, gambar, suara, dan video. Dengan demikian, piranti lunak ini bisa mengakomodasi semua kegiatan pembelajaran bahasa rekursif dan interaktif seperti mendengarkan, membaca, menulis dan juga bermain language games. Tampilan yang dihasilkan dari rekursif dan interaktif ini bisa semenarik program yang dibangun dengan rekursif dan interaktif yang canggih. 3.2. Saran Semoga makalah ini dapat bermanfaat bagi pembaca dan agar dapat mengetahui dan memahami materi Matematika Diskrit tentang Fungsi Rekursif. Jika ada kesalahan dalam penulisan makalah ini penulis mengharapkan kritikan atau saran dari pembaca.
DAFTAR PUSTAKA http://tarman-soetarman.blogspot.com/2011/04/makalah-rekursif-dan-iterarif.html http://nciperz.blogspot.com/2016/12/rekursif-matematika-diskrit_15.html https://asepsumpena09.wordpress.com/2014/11/08/definisi-fungsi-rekursif-dan-contohnya/ https://www.slideshare.net/ayukwuland/relasi-rekursif-bagian-i
8