Contoh-contoh Barisan Rekursif

Rekursi adalah salah satu ide penting dalam ilmu komputer. Untuk menyelesaikan suatu masalah secara rekursif, kita harus memecah masalah tersebut menjadi beberapa submasalah yang masing-masing memiliki bentuk yang sama dengan masalah awal. Untuk melakukan hal ini, kita harus menemukan suatu cara sedemikian sehingga ketika proses diulang beberapa kali, submasalah terakhir menjadi mudah diselesaikan dan solusi dari submasalah-submasalah yang terbentuk dapat dihimpun bersama untuk membentuk solusi dari masalah aslinya.

Mungkin bagian tersulit dalam memecahkan masalah secara rekursif adalah ketika pada tahap menentukan bagaimana mengetahui solusi dari submasalah-submasalah tersebut akan memberikan solusi pada masalah asli secara keseluruhan. Andaikan kita tahu solusi dari submasalahnya, bagaimana kita menggunakan solusi tersebut untuk menyelesaikan permasalahan yang lebih luas merupakan hal yang tidak mudah. Anggapan bahwa submasalah yang sudah terselesaikan ini biasa disebut sebagai anggapan perulangan rekursif. Anggapan perulangan rekursif ini serupa dengan hipotesis induksi pada pembuktian dengan induksi matematika.

Contoh 1: Menara Hanoi

Pada tahun 1883 seorang matematikawan berkebangsaan Prancis, Édouard Lucas, menemukan suatu permainan yang disebut Menara Hanoi (La Tour D’Hanoï). Permainan ini memiliki 8 cakram kayu dengan lubang di tengahnya, yang disusun dari ukuran terkecil ke terbesar pada salah satu tiang dari total 3 tiang yang ada. Jiplakan sampul dari kotak Menara Hanoi waktu itu dapat dilihat pada gambar berikut.

Sampul Menara Hanoi

Pemain dari permainan ini diminta untuk memindahkan semua cakram dari tiang satu ke tiang lainnya, dengan tidak menempatkan cakram yang lebih besar di atas cakram yang lebih kecil. Aturan dari permainan ini didasarkan pada legenda di India:

Pada tangga dari altar kuil di Benares, selama bertahun-tahun lamanya, Brahmana telah memindahkan menara 64 cakram emas dari satu tiang ke tiang lainnya; satu demi satu, dan tidak pernah sama sekali menempatkan cakram yang lebih besar di atas cakram yang lebih kecil. Ketika semua cakram tersebut sudah dipindahkan, maka Brahmana akan jatuh, dan itu merupakan akhir dari dunia.

Pada waktu itu, permainan ini menawarkan hadiah sebesar 10 ribu franc (atau sekitar 13 juta rupiah) kepada siapa saja yang dapat memindahkan 64 cakram dengan menggunakan tangan dan dengan mengikuti aturan permainan ini. Andaikan kamu memindahkan cakram-cakram tersebut dengan langkah-langkah yang seefisien mungkin, berapa langkah yang kamu butuhkan untuk memenangkan hadiah tersebut?

Pembahasan Untuk menyelesaikan permasalahan menara Hanoi di atas, sebaiknya kita perumum permasalahannya untuk n adalah banyaknya cakram yang akan dipindahkan. Untuk memindahkan semua cakram dari satu tiang ke tiang lainnya, perhatikan ilustrasi berikut.

Langkah-langkah Menara Hanoi

Pada gambar (i), terdapat n cakram yang harus dipindahkan ke tiang yang lainnya. Misalkan, banyaknya langkah yang harus dilakukan untuk memindahkan n cakram tersebut kita simbolkan dengan mn. Pertama, kita harus memindahkan sejumlah n – 1 cakram teratas ke tiang lainnya, misalkan tiang C. Sehingga, banyaknya langkah yang harus kita lakukan adalah mn – 1 (gambar (ii)). Selanjutnya, kita pindah satu cakram yang tersisa ke tiang B (tiang yang masih kosong). Untuk memindahkan satu cakram tersebut, kita melakukan 1 langkah. Dan terakhir, kita pindahkan sejumlah n – 1 cakram pada tiang C ke tiang B. Proses ini membutuhkan mn – 1 langkah. Sehingga, banyaknya langkah yang diperlukan untuk memindahkan n cakram dapat dirumuskan sebagai berikut.

Contoh 1 Relasi Rekursif

Untuk menentukan kondisi awalnya, kita perhatikan kembali definisi dari barisan tersebut. Karena hanya 1 langkah yang diperlukan untuk memindahkan 1 cakram dari satu tiang ke tiang lainnya, maka

Contoh 1 m1

Sehingga, barisan m1, m2, m3, …, dapat didefinisikan secara rekursif sebagai berikut: Untuk semua bilangan bulat n ≥ 2

Contoh 1 Barisan Rekursif

Berikut ini perhitungan dari 5 suku selanjutnya.

Contoh 1 Suku-suku Selanjutnya

Kembali kepada legenda India, misalkan kita memindahkan cakram-cakram tersebut dengan kecapatan 1 langkah setiap detik. Maka waktu yang diperlukan dari awal penciptaan sampai akhir dunia adalah m64 detik. Untuk menentukan m64, kita dapat menggunakan kalkulator untuk melanjutkan proses di atas. Nilai dari m64 adalah sekitar,

Contoh 1 m64

Dan tahukah kamu, nilai di atas, 584,5 miliar tahun, mendekati usia semesta kita yang yang diperoleh dengan menggunakan kajian ilmiah!

Tentang Yosep Dwi Kristanto

Tahun 2012 memulai blogging untuk menyediakan sumber belajar matematika online, yang semoga dapat memberikan kontribusi bagi pendidikan di Indonesia. Pengagum pendekatan kontekstual dalam proses pembelajaran.
Pos ini dipublikasikan di Matematika Diskrit, Topik Matematika dan tag , , , , , , . Tandai permalink.

2 Balasan ke Contoh-contoh Barisan Rekursif

  1. Ping balik: Menyelesaikan Relasi Rekursif dengan Iterasi | Asiknya Belajar Matematika

  2. Ping balik: Menyelesaikan Relasi Rekursif dengan Iterasi | Pendidikan Matematika

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s