REKURSI

1 PENGERTIAN REKURSI
            Rekursi berarti suatu proses yang bisa memanggil dirinya sendiri. Dalam rekursi terkandung pengertian prosedur atau fungsi. Perbedaannya adalah rekursi bisa memanggil ke dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi.

2 PROSES REKURSIF
            Untuk memahami proses rekursif yang terjadi dalam sebuah fungsi rekursi, perhatikan contoh dibawah ini :
                    function FAKT (N : integer) : integer;
                    begin
                           if N = 0 then
                               FAKT := 1
                           else
                               FAKT := N * FAKT (N – 1)
                      end;

3 MENYUSUN PERMUTASI
              Contoh lain dari proses rekursif adalah untuk menyusun semua permutasi yang mungkin dari sekelompok karakter. Sebagai contoh, jika kita mempunyai 3 buah karakter A, B, C, maka permutasi yang mungkin dari ketiga karakter ini adalah :
          A B C         B A C         C A B
          A C B         B C A         C B A
Secara umum, banyaknya permutasi dari N buah karakter adalah N faktorial. Dalam contoh diatas N = 3, sehingga banyaknya permutasi adalah 3 ! = 6.
Proses penyusunan permutasinya bisa dijelaskan sebagai berikut :

•  Cetak elemen ke 1, dan cetak permutasi elemen ke 2 sampai N ( permutasi dengan N – 1 elemen)
• Cetak elemen ke 2, dan cetak permutasi elemen ke 1, elemen ke 3 sampai N ( permutasi dengan N – 1 elemen)
• Cetak elemen ke 3, dan cetak permutasi elemen ke 1, elemen ke 2, elemen ke 4 sampai N ( permutasi dengan N – 1 elemen)
• dan seterusnya, sampai langkah terakhir adalah cetak elemen ke N, dan cetak permutasi elemen ke 1 sampai elemen ke (N – 1) ( permutasi dengan N – 1 elemen)

          Proses diulang terus sampai dicetak permutasi dengan 1 elemen. Sebagai contoh, untuk N = 3, maka caranya adalah :

• Cetak ’A’, dan cetak permutasi (’B’ ’C’);
• Cetak ’B’, dan cetak permutasi (’A’ ’C’);
• Cetak ’C’, dan cetak permutasi (’A’ ’B’);

4 MENARA HANOI
          Contoh klasik dari proses rekursif adalah permainan Menara Hanoi, berdasarkan legenda pertama kali dimainkan secara manual oleh seorang pendeta Budha di Hanoi. Dalam permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satu tonggak ke tonggak lain, dan diperbolehkan melewati tonggak bantuan.
           Aturan permainannya adalah sebagai berikut. Semua piringan pada tonggak A akan dipindah pada tonggak C dengan ketentuan bahwa pemindahan piringan dilakukan satu persatu dan piringan yang lebih besar tidak boleh diletakkan diatas piringan yang lebih kecil.

Secara sederhana, pemindahan seluruh piringan secara rekursif dapat dilaksanakan dengan :

1. Pindahkan (N – 1) piringan yang paling atas dari tonggak asal (A) ke tonggak bantu (B).
2. Pindahkan piringan ke N (piringan terakhir) dari tonggak asal (A) ke tonggak tujuan (C).
3. Pindahkan (N – 1) piringan dari tonggak bantu (B) ke tonggak tujuan (C).

          Tetapi tentu saja piringan sebanyak (N – 1) buah tidak boleh dipindah bersama-sama, tetapi harus satu per satu. Untuk mempermudah penyelesaian persoalan kita coba membuat satu notasi baru, misalnya :
                               MENARA (N, Asal, Bantu, Tujuan)

          Notasi diatas bisa dibaca “Pindahkan N buah piringan dari tonggak Asal ke tonggak Tujuan menggunakan tonggak Bantu”. Jika N = 1, maka notasi diatas bisa ditulis sebagai :
                              MENARA (1, Asal, Bantu, Tujuan)

           yang secara langsung bisa kita laksanakan dengan memindahkan piringan dari tempat Asal ke tempat Tujuan. Untuk N > 1, penyelesaiannya bisa kita pecah menjadi 3 penyelesaian seperti diatas, yaitu :
                              MENARA (N – 1, Asal, Tujuan, Bantu);
                              MENARA (N, Asal, Bantu, Tujuan); atau Asal => Tujuan
                              MENARA (N – 1, Bantu, Asal, Tujuan);

Contoh : Menara Hanoi dengan 4 buah piringan.
MENARA (4, A, B, C)
yang setelah dihitung perlu 15 kali perpindahan, yaitu :
        A => B        A => C        B => C         A => B        C => A
        C => B        A => B        A => C         B => C        B => A
        C => A        B => C        A => B         A => C        B => C