Contoh Soal dan Pembahasannya: Matematika Diskrit Rekursif - Solusi Khusus
Matematika diskrit, khususnya rekursi, seringkali menjadi tantangan bagi banyak mahasiswa. Konsep rekursi, dengan definisi yang bergantung pada dirinya sendiri, membutuhkan pemahaman yang mendalam. Artikel ini akan membahas beberapa contoh soal dan penyelesaiannya untuk membantu Anda menguasai topik ini. Kita akan fokus pada solusi khusus, memberikan langkah-langkah detail untuk setiap masalah.
Memahami Rekursi
Sebelum kita menyelami contoh soal, mari kita ingat kembali definisi rekursi. Suatu fungsi dikatakan rekursif jika definisinya merujuk pada dirinya sendiri. Ini melibatkan dua bagian utama:
- Basis Kasus (Base Case): Kondisi yang menghentikan rekursi. Tanpa basis kasus, rekursi akan berjalan tanpa henti (infinite loop).
- Langkah Rekursif (Recursive Step): Definisi fungsi yang merujuk pada dirinya sendiri dengan input yang lebih kecil atau lebih sederhana.
Contoh Soal dan Pembahasan
Berikut beberapa contoh soal matematika diskrit yang melibatkan rekursi, beserta pembahasannya yang detail:
Soal 1: Mencari Suku ke-n Barisan Fibonacci
Barisan Fibonacci didefinisikan sebagai berikut: F(0) = 0, F(1) = 1, dan F(n) = F(n-1) + F(n-2) untuk n β₯ 2. Tentukan nilai F(5).
Pembahasan:
Kita akan menggunakan definisi rekursif untuk menghitung F(5):
- F(0) = 0
- F(1) = 1
- F(2) = F(1) + F(0) = 1 + 0 = 1
- F(3) = F(2) + F(1) = 1 + 1 = 2
- F(4) = F(3) + F(2) = 2 + 1 = 3
- F(5) = F(4) + F(3) = 3 + 2 = 5
Jadi, nilai F(5) adalah 5.
Soal 2: Menghitung Faktorial
Faktorial dari suatu bilangan bulat positif n, dilambangkan dengan n!, didefinisikan sebagai hasil kali semua bilangan bulat positif dari 1 hingga n. Tuliskan fungsi rekursif untuk menghitung faktorial dan hitung 5!.
Pembahasan:
Fungsi rekursif untuk menghitung faktorial dapat ditulis sebagai berikut:
factorial(n) =
1, jika n = 0
n * factorial(n-1), jika n > 0
Mari kita hitung 5!:
- factorial(5) = 5 * factorial(4)
- factorial(4) = 4 * factorial(3)
- factorial(3) = 3 * factorial(2)
- factorial(2) = 2 * factorial(1)
- factorial(1) = 1 * factorial(0)
- factorial(0) = 1
Dengan demikian:
factorial(5) = 5 * 4 * 3 * 2 * 1 = 120
Jadi, 5! = 120.
Soal 3: Menghitung Tower of Hanoi
Tower of Hanoi adalah teka-teki matematika klasik yang melibatkan memindahkan tumpukan cakram dari satu tiang ke tiang lain dengan aturan tertentu. Tuliskan fungsi rekursif untuk menghitung jumlah langkah minimum yang dibutuhkan untuk memindahkan n cakram.
Pembahasan:
Rumus rekursif untuk menghitung langkah minimum dalam Tower of Hanoi adalah:
Hanoi(n) = 2 * Hanoi(n-1) + 1, dengan Hanoi(1) = 1
Mari kita hitung langkah minimum untuk memindahkan 3 cakram:
- Hanoi(3) = 2 * Hanoi(2) + 1
- Hanoi(2) = 2 * Hanoi(1) + 1 = 2 * 1 + 1 = 3
- Hanoi(3) = 2 * 3 + 1 = 7
Jadi, dibutuhkan 7 langkah minimum untuk memindahkan 3 cakram.
Kesimpulan
Memahami konsep rekursi dalam matematika diskrit sangat penting. Dengan latihan yang cukup dan pemahaman yang mendalam tentang basis kasus dan langkah rekursif, Anda dapat dengan mudah menyelesaikan berbagai masalah yang melibatkan rekursi. Semoga contoh soal dan pembahasan di atas dapat membantu Anda meningkatkan kemampuan dalam memecahkan masalah matematika diskrit yang berkaitan dengan rekursi. Jangan ragu untuk berlatih lebih banyak soal untuk memperdalam pemahaman Anda!
