Rekursif

Rekursif

// Sejarah Singkat Barisan Rekursif "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.

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.

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 m_n. Pertama, kita harus memindahkan sejumlah n – 1 cakram teratas ke tiang lainnya, misalkan tiang C. Sehingga, banyaknya langkah yang harus kita lakukan adalah m_{n – 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 m_{n – 1} langkah. Sehingga, banyaknya langkah yang diperlukan untuk memindahkan n cakram dapat dirumuskan sebagai berikut.

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

Sehingga, barisan m₁, m₂, m₃, …, dapat didefinisikan secara rekursif sebagai berikut: Untuk semua bilangan bulat n ≥ 2

Berikut ini perhitungan dari 5 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 m₆₄ detik. Untuk menentukan m₆₄, kita dapat menggunakan kalkulator untuk melanjutkan proses di atas. Nilai dari m₆₄ adalah sekitar,

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

-------------------------------------------------------------------------------

1. penjelasan tentang rekursif

• Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri.

• Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri.
• Fungsi ini akan terus berjalan sampai kondisi berhenti terpenuhi, oleh karena itu dalam sebuah fungsi rekursif perlu terdapat 2 blok penting, yaitu blok yang menjadi titik berhenti dari sebuah proses rekursi dan blok yang memanggil dirinya sendiri.

• Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi
• fungsi rekursif ini mirip dengan perulangan, jadi kelebihan/manfaatnya yaitu pada penghematan penulisan listing program jika dibandingkan dengan looping/perulangan.

2. Contoh penggunaan proses rekursif

• Masalah : Memotong roti tawar tipis-tipis sampai habis

• Algoritma :

1. Jika roti sudah habis atau potongannya sudah paling tipis maka pemotongan roti selesai
2. jika roti masih bisa dipotong, potong tipis dari tepi roti tersebut
3. lakukan prosedur 1 dan 2 untuk sisa potongannya

3.  contoh fungsi rekursif :
1. fungsi pangkat
2. Konsep Menara Hanoi
3. fungsi faktorial
4. deret fibonacci

4. Kelebihan perulangan rekursif :
1. Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar
2. Dapat melakukan perulangan dengan batasan fungsi

5. Kekurangan perulangan rekursif :
1. Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja
2. Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk

6. contoh program fungsi rekursif faktorial 

Fungsi diatas adalah fungsi untuk mencari nilai faktorial dari angka yang dilambangkan dengan int x. Mengapa fungsi diatas termasuk Rekursif? Karena didalam code tersebut fungsi faktorial memanggil dirinya sendiri pada saat pemanggilan angka berikutnya faktorial (x-1) . Misal angka  yang diinputkan adalah 4 maka faktorial (x-1) = 3. dan perulangan itu akan berhenti jika tidak memenuhi syarat lagi.

cout<<"Terima Kasih Atas Kunjungannya =)) ";

Untuk memulai bahasan rekursi, kita membahas sebuah masalah sederhana yang kemungkinan kita tidak berpikir untuk menyelesaikan dengan cara rekursif. Yaitu permasalahan faktorial, yang mana kita menghitung hasil faktorial dari sebuah bilangan, yaitu n. - See more at: http://aina-tunk.blogspot.com/2012/06/program-rekursif-faktorial-pada-c.html#sthash.8qlTRjtU.dpuf

Untuk memulai bahasan rekursi, kita membahas sebuah masalah sederhana yang kemungkinan kita tidak berpikir untuk menyelesaikan dengan cara rekursif. Yaitu permasalahan faktorial, yang mana kita menghitung hasil faktorial dari sebuah bilangan, yaitu n. Faktorial dari n (ditulis n!), adalah hasil kali dari bilangan tersebut dengan bilangan di bawahnya, di bawahnya hingga bilangan 1. Sebagai contoh, 4! = (4)(3)(2)(1).

contoh :

  3!=3.(3-1)!

  3!=3.2!     -->   Faktorial n-1

  3!=3.2.(2-1)!

  3!=3.2.1!   -->  Faktorial n-2

  3!=3.2.1

- See more at: http://aina-tunk.blogspot.com/2012/06/program-rekursif-faktorial-pada-c.html#sthash.8qlTRjtU.dpuf