Implementasi Tower of Hanoi Menggunakan Rekursi pada Program Java

• Rekursi

         Rekursi adalah salah satu metode untuk menyelesaikan masalah dengan menyederhanakan masalah tersebut menjadi bagian-bagian yang lebih kecil. Fungsi rekursi merupakan fungsi yang memanggil dirinya sendiri hingga mencapai base case (kondisi dimana fungsi rekursi akan selesai dipanggil agar tidak terjadi infinite recursion).

• Tower of Hanoi

         Tower of Hanoi adalah permainan teka-teki matematika yang terdiri dari 3 menara/tiang dan sejumlah cincin/piringan yang memiliki ukuran yang berbeda-beda dan disusun mengerucut dengan piringan yang paling kecil ukurannya berada di tumpukan teratas, sedangkan piringan yang berukuran paling besar berada di tumpukan terbawah.

      Tujuan dari permainan ini adalah memindahkan semua tumpukan piringan dari suatu tiang ke tiang yang lain tanpa melanggar aturan sebagai berikut:

1. Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
2. Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain.
3. Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.

     Tower of Hanoi ini dapat diselesaikan dengan minimum 2^n - 1 langkah dengan n merupakan jumlah piringan yang ingin dipindahkan, dianggap ada 3 menara yaitu source, auxiliary, dan target, penyelesaiannya dengan menggunakan algoritma:

1. Pindahkan n-1 piringan teratas dari source ke auxiliary.
2. Pindahkan piringan yang tersisa di source ke target.
3. Pindahkan seluruh piringan dari auxiliary ke target.
4. Jika piringan berjumlah 0/tidak ada yang tersisa, maka rekursi telah mencapai base case sehingga rekursi telah berhenti.

         Ilustrasi: 

        Source Code :

        Berikut adalah keluaran alur dari program Tower of Hanoi :