REKURSI

REKURSI

Apa itu REKURSI ???

Suatu obyek disebut sebagai rekursif apabila sebagian berisi atau didefinisikan sebagai dirinya sendiri. Dengan demikian rekursif adalah suatu proses berupa pemanggilan diri berupa statement perulangan. Proses rekursif juga memungkinkan terjadinya komputasi yang tidak berkesudahan sampai memory yang digunakan tidak dapat menampung lagi, sehingga perlu diperhatikan akan adanya kondisi untuk menghentikan proses eksekusi program . Sebagai contoh sederhana mengenai proses rekursif adalah proses menghitung nilai faktorial dari bilangan bulat positif dan mencari deret fibonnaci dari suatu bilangan bulat, permainan menara hanoi dan sebagainya. II-12
Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer. Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa.

Cara lain untuk menyelesaikan permasalahan di atas adalah dengan cara rekursi, dimana n! adalah hasil kali dari n dengan (n-1)!. Untuk menyelesaikan (n-1)! adalah sama dengan n!, sehingga (n-1)! adalah n-1dikalikan dengan (n-2)!, dan (n-2)! adalah n-2 dikalikan dengan (n-3)! dan seterusnya sampai dengan n = 1, kita menghentikan penghitungan n! Cara rekursif untuk permasalahan ini, secara umum dapat kita detailkan sebagai berikut:

1 jika n=0, n=1

F(n) =

nF(n-1) jika n>1

dua fase dasar dari sebuah proses rekursi: fase awal dan fase balik. Dalam fase awal, masing-masing proses memanggil dirinya sendiri. Fase awal ini berhenti ketika pemanggilan telah mencapai kondisi terminal. Sebuah kondisi teminate adalah kondisi dimana sebuah fungsi rekursi kembali dari pemanggilan, artinya fungsi tersebut sudah tidak memanggil dirinya sendiri

dan kembali pada sebuah nilai. Sebagai contoh, dalam penghitungan faktorial dari n, kondisi terminal adalah n = 1, n = 0. Untuk setiap fungsi rekursi, minimal harus ada satu kondisi terminal. Setelah fase awal selesai, kemudian proses melanjutkan pada fase balik, dimana fungsi sebelumnya akan dikunjungi lagi dalam fase balik ini. Fase ini berlanjut sampai pemanggilan awal, hingga secara lengkap proses telah berjalan.

Rekursi Tail

Sebuah proses rekursi dikatakan rekursi tail jika pernyataan terakhir yang akan dieksekusi berada dalam tubuh fungsi dan hasil yang kembali pada fungsi tersebut bukanlah bagian dari fungsi tersebut. Ciri fungsi rekursi tail adalah fungsi tersebut tidak memiliki aktivitas selama fase balik. Ciri ini penting, karena sebagian besar compiler modern secara otomatis membangun kode untuk menuju pada fase tersebut. Ketika kompiler mendeteksi sebuah pemanggilan yang mana adalah rekursi tail, maka kompiler menulis aktivitas yang ada sebagai sebuah record yang dimasukkan ke dalam stack. Kompiler dapat melakukan hal tersebut karena pemanggilan rekursi adalah pernyataan terakhir yang dieksekusi dalam aktivitas yang sedang berlangsung, sehingga tidak ada aktivitas yang harus dikerjakan pada saat pemanggilan kembali. Untuk memahami bagaimana sebuah rekursi tail bekerja, kita akan kembali membahas tentang penghitungan komputasi dari faktorial secara rekursi. Sebagai langkah awal, akan sangat membantu jika kita memahami alasan dalam definisi awal yang bukan rekursi tail. Dimana dalam definisi tersebut, penghitungan n! adalah dengan mengalikan n dengan (n-1)! dalam setiap aktivitas, yang mana hal tersebut terus diulang dari n = n –1 sampai n = 1. Definisi ini bukanlah rekursi tail karena nilai yang dikembalikan dalam setiap aktivitas bergantung pada perkalian n dengan nilai yang dikembalikan oleh aktivitas sesudahnya. Oleh karena itu, pencatatan aktivitas dari masing-masing pemanggilan harus diingat dalam stack sampai nilai-nilai yang dikembalikan dalam aktivitas-aktivitas sesudahnya telah terdefinisi. Sekarang marilah kita melihat bagaimana rekursi tail didefinisikan untuk menghitung n!, yang secara formal kita definisikan sebagai berikut:

a jika n=0, n=1

F(n,a) =

F(n-1,na) jika n>1

Pada definisi ini digunakan parameter kedua, yaitu a, yang mana merupakan nilaiutama dari penghitungan faktorial secara rekursif. Hal ini mencegah kita untuk mengalikan nilai yang dikembalikan dalam setiap aktivitas dengan n. Dalam masingmasing pemanggilan rekursi kita mendefinisikan a = na dan n = n – 1. Kita melanjutkan sampai n = 1, sebagai kondisi terminal. Dalam gambar 5.2 menggambarkan proses komputasi 4! dengan menggunakan rekursi tail. Perhatikan bahwa di sana tidak ada aktivitas selama fase balik.

Kesimpulan

1. Rekursi adalah kemampuan suatu rutin untuk memanggil dirinya sendiri.

2. Penggunaan sebuah rekursi harus mendefinisikan kondisi terminal, jika tidak

eksekusi program tidak pernah berhenti, sehingga penggunaan memori

tumpukan habis dan komputer akan hang.

3. Dalam beberapa situasi, pemecahan secara rekursif mempunyai keuntungan

dan kekurangan yang dapat diperbandingkan dengan cara iteratif.

Referensi:

http://lecturer.eepis-its.edu/~entin/Struktur%20Data%20&%20Algoritma/buku/Data%20Structure%20-%20Bab%205.pdf

This entry was posted in Uncategorized. Bookmark the permalink.

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