Rekursi: Towers of Hanoi


Salah satu studi kasus yang paling terkenal dalam pembelajaran bab fungsi rekursi adalah Towers of Hanoi (Menara Hanoi). Konon menurut sebuah literatur, di daerah Hanoi (Vietnam) terdapat sebuah kuil yang melombakan pemindahan piringan-piringan dari sebuah tiang ke tiang yang lain. Perlombaan tersebut diikuti oleh para biksu.

Aturan mainnya adalah memindah piringan hanya boleh satu saja sekali angkat untuk dipindahkan ke tiang lain. Tiang yang disediakan sejumlah 3 buah, salah satunya adalah tiang bantuan. Di tiang asal terdapat sejumlah piringan yang telah tersusun dengan urut dari besar kemudian semakin ke atas semakin mengecil. Tujuannya adalah memindahkan semua piringan ke tiang tujuan dengan posisi yang kembali urut sebagaimana semula. Selama pemindahan tidak diperbolehkan ada susunan piringan yang mana piringan yang lebih kecil berada di bawah yang lebih besar.

Berikut ini adalah contoh source code programnya dalam bahasa Java untuk menyelesaikan kasus tersebut. Dengan teknik rekursi, program menjadi lebih sederhana namun sangat powerfull untuk menyelesaikan permasalahan:

public class hanoi
{
static int langkah;
public static void towers( int n, char from, char to, char aux)
{
if ( n == 1 ) {
langkah++;
System.out.println(langkah + “. Pindahkan disk 1 dari “+ from +” ke “+ to);
return;
}
towers( n – 1, from, aux, to );
langkah++;
System.out.println(langkah + “. Pindahkan disk “+ n +” dari “+ from +” ke “+ to);
towers( n – 1, aux, to, from );
}
public static void main(String[] args) {
towers(3,’A’,’C’,’B’);
}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: