Towers of Hanoi atau menara hanoi merupakan contoh permasalahan yang boleh diselesaikan dengan fungsi rekursif, apa itu fungsi rekursif? fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Fungsi rekursif dipakai karena memiliki kelebihan yaitu penulisan baris program lebih singkat. Akan tetapi, fungsi ini juga memiliki kekurangan, yaitu membutuhkan banyak memori karena setiap kali program bagian dipanggil oleh dirinya sendiri, dibutuhkan sejumlah memori tambahan.
Towers of Hanoi ini melibatkan pemindahan beberapa keping cakram yang berlainan ukuran dari tiang satu ke tiang yang lain. ketika akan memindahkan semua keping dari tiang A ke tiang C ada syarat yang harus dipenuhi, yaitu :
- Setiap pemindahan hanya satu keping cakram yang boleh dipindahkan
- Keping cakram yang ukurannya lebih kecil selalu harus ada diatas keping cakram yang ukurannya besar
Mari kita coba menyelesaikan langkah-langkah memindahkan keping cakram dari tiang A ke tiang C. :
kondisi awal :
*tiang B digunakan sebagai tempat transit yang dapat digunakan
- Himpunan Kandidat yang terdapat dalam menara tersebut 1, 4, 3, 5, 4, 6, 2
- Himpunan Solusi : Keping cakram yang berada di tiang A akan pindah ke tiang C sesuai syarat tersusunnya Towers of Hanoi
- Fungsi seleksinya yaitu keping cakram akan tersusun di tiang C dari keping cakram berukuran besar hingga ukurannya kecil
- Fungsi kelayakan keping cakram yang berukuran besar tidak boleh diletakan diatas keping cakram yang berukuran lebih kecil
langkahnya:
- Keping cakram 1 pindah dari tiang a ke b
- Keping cakram 4 pindah dari tiang a ke c
- Keping cakram 3 pindah dari tiang a ke c
- Keping cakram 1 pindah dari tiang b ke c
- Keping cakram 5 pindah dari tiang a ke b
- Keping cakram 4 pindah dari tiang a ke b
- Keping cakram 1 pindah dari tiang c ke a
- Keping cakram 3 pindah dari tiang c ke b
- Keping cakram 1 pindah dari tiang a ke b
- Keping cakram 4 pindah dari tiang c ke a
- Keping cakram 1 pindah dari tiang b ke a
- Keping cakram 3 pindah dari tiang b ke c
- Keping cakram 1 pindah dari tiang a ke b
- Keping cakram 3 pindah dari tiang c ke a
- Keping cakram 1 pindah dari tiang b ke a
- Keping cakram 4 pindah dari tiang c ke b
- Keping cakram 1 pindah dari tiang a ke c
- Keping cakram 3 pindah dari tiang a ke b
- Keping cakram 1 pindah dari tiang c ke b
- Keping cakram 6 pindah dari tiang a ke c
- Keping cakram 1 pindah dari tiang b ke a
- Keping cakram 3 pindah dari tiang b ke c
- Keping cakram 1 pindah dari tiang a ke b
- Keping cakram 2 pindah dari tiang a ke c
- Keping cakram 1 pindah dari tiang b ke c
- Keping cakram 4 pindah dari tiang b ke a
- Keping cakram 4 pindah dari tiang b ke a
- Keping cakram 1 pindah dari tiang c ke a
- Keping cakram 2 pindah dari tiang c ke b
- Keping cakram 1 pindah dari tiang a ke b
- Keping cakram 3 pindah dari tiang c ke a
- Keping cakram 1 pindah dari tiang b ke c
- Keping cakram 2 pindah dari tiang b ke a
- Keping cakram 1 pindah dari tiang c ke a
- Keping cakram 5 pindah dari tiang b ke c
- Keping cakram 1 pindah dari tiang a ke c
- Keping cakram 2 pindah dari tiang a ke b
- Keping cakram 1 pindah dari tiang c ke b
- Keping cakram 3 pindah dari tiang a ke c
- Keping cakram 1 pindah dari tiang b ke c
- Keping cakram 2 pindah dari tiang b ke a
- Keping cakram 1 pindah dari tiang c ke a
- Keping cakram 3 pindah dari tiang c ke b
- Keping cakram 1 pindah dari tiang a ke c
- Keping cakram 2 pindah dari tiang a ke b
- Keping cakram 1 pindah dari tiang c ke b
- Keping cakram 4 pindah dari tiang a ke c
- Keping cakram 4 pindah dari tiang a ke c
- Keping cakram 1 pindah dari tiang b ke c
- Keping cakram 2 pindah dari tiang b ke a
- Keping cakram 1 pindah dari tiang c ke a
- Keping cakram 3 pindah dari tiang b ke c
- Keping cakram 1 pindah dari tiang a ke b
- Keping cakram 2 pindah dari tiang a ke c
- Keping cakram 1 pindah dari tiang b ke c
Setelah selesai melakukan langkah-langkah tersebut, maka hasil akhirnya keping cakram akan pindah ke tiang c dan tersusun dari keping cakram yang ukurannya besar hingga keping cakram yang ukurannya kecil. Berikut gambarnya :
