Recursive

Definisi Recursive 

 

Recursive adalah proses pemanggilan dirinya sendiri (fungsi atau prosedur). Fungsi maupun prosedur yang memanggil dirinya disebut fungsi atau prosedur rekursif. Fungsi untuk suatu bagian program yang mengembalikan (menghasilkan) hanya satu nilai. Sebuah function call adalah suatu ekspresi jadi ia memberikan satu nilai.Procedure adalah suatu bagian program yang melakukan aksi/fungsi khusus, biasanya berdasarkan sekumpulan parameter. Sebuah procedure call adalah suatu statemen, jadi ia melakukan aksi. Banyak obyek dalam matematika didefinisikan dengan menampilkan suatu proses untuk  menghasilkan obyek-obyek tsb.

Misalnya : n faktorial (n!) didefinisikan sebagai produk dari semua integer diantara n dan 1. Contoh lain adalah bilangan asli. 1 adalah bilangan asli.Successor dari 1 adalah bilangan asli.

Perbedaan rekursi dengan prosedur/fungsi adalah rekursi bisa memanggil kedirinya sendiri tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur/fungsi. Ciri masalah yang dapat diselesaikan secara rekursif adalah masalah tersebut dapat direduksi menjadi satu atau lebih masalah-masalah serupa yang lebih kecil. Secara umum suatu algoritma rekursif selalu mengandung 2 macam kasus :

1. satu atau lebih kasus yang pemecahan masalahnya dilakukan dengan menyelesaikan masalah serupa yg lebih sederhana (menggunakan recursive call).
2. satu atau lebih kasus pemecahan masalahnya dilakukan tanpa recursive call. Kasus ini disebut kasus dasar atau penyetop. Supaya tidak terjadi rekursif tak hingga, maka setiap langkah rekursif haruslah mengarah ke kasus penyetop.

Sistem komputer mengikuti jalannya program yang rekursif biasanya dengan menggunakan suatu struktur data yang disebut stack. Ketika eksekusi program sampai pada suatu rekursif call, ia menghentikan sementara komputasi yg sedang dilaksanakannya sekarang untuk melakukan recursive call tsb, agar ia dapat kembali ke keadaan semula setelah recursive call itu selesai , ia harus menyimpan informasi yang cukup. Informasi yg diperlukan disebut activation frame.  Activation frame disimpan pada bagian memori yg diatur dalam benruk stack.  Rekursif yang berlapis-lapis dapat menghabiskan memori yang mengakibatkan stack overflow.  Masalah yg mempunyai solusi rekursif juga mempunyai solusi iteratif(menggunakan loop).  Versi iteratif seringkali lebih efisien daripada versi rekursif karena rekursif biasanya menggunakan memori yg lebih besar dan memerlukan waktu ekstra u/ penanganan stack of activation frame.

Contoh 1 menghitung faktorial :

Hasil Outputnya

Parameter and local Variable

Stacks  adalah Struktur data dimana data yang terkhir masuk adalah data yang akan diproses terlebih dahulu. Stack biasanya dimplementasikan dengan menggunakan sebuah array,dalam stack kita bisa menambah data dengan perintah operasi push,dan menghapus data dengan menggunakan perintah operasi pop

Fungsi Rekursi pada Matematika

Banyak fungsi matematika yang dapat didefinisikan dengan rekursi.

Contoh: fungsi faktorial dari n (n!), dapat didefinisikan secara iteratif :

0! Adalah 1 dan  n! Adalah n x (n-1)!, untuk n>0

Misal: 4! Adalah 4 x 3!, yang artinya 4 x 3 x 2 x 1, atau 24

Iteratif  dan  rekursi

1.      Persamaan dan perbedaan Iteraktif dan rekursif

• Persamaan

          Sama-sama merupakan bentuk perulangan

          Dilakukan pengecekan kondisi terlebih dahulu sebelum mengulang

• Perbedaan

          Pada rekursi, dikenal adanya istilah recursive step

          Sedangkan pada iteratif ada decrement

Kelebihan dan kekurangan recursive

• Kelebihan

          solusi sangatlah efisien

          dapat memecahkan masalah yang sulit dengan tahapan yang mudah dan singkat

• Kelemahan

          sulit dipahami

          perlu stack besar (stack overrun)

Kasus Menara Hanoi 

Definisi menara hanoi

Menara Hanoi adalah problem di mana kita harus memindahkan balok yang mempunyai perbedaan ukuran dari suatu menara (tower) ke menara lainnya.

Masalah  :

1. Memindahkan n balok dari menara A ke menara C menggunakan menara B bila dibutuhkan.

2. Hal yang harus dicermati :

Hanya satu buah balok saja yang dapat dipindahkan dalam satu waktu  balok yang lebih besar tidak boleh diletakkan di atas balok yang lebih kecil

Referensi:

 http://informatika11d.wordpress.com/2012/11/24/struktur-data-recursive/