Struktur Data – Recursive


 

9.1     Recursive

9.1.1 Definisi Recursive

Recursive adalah proses pemanggilan dirinya sendiri (fungsi atau prosedur). Fungsi maupun prosedur yang memanggil dirinya disebut fungsi atau prosedur rekursif. Fungsi antuk 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 :

n ! = 1 jika n = 0 atau n=1

n ! = n * (n-1) * (n-2) *…* 1, jika n > 0

 

9.1.2   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

  1.   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

             

  1.   Fungsi rekursi untuk faktorial

Program :

//menghitung n! Menggunakan definisi rekursi

//pre : n>=0

int factorial (int n){

int ans;

if (n == 0)

ans = 1;

else

ans = n * factorial (n-1);           return(ans);

}

 

  1.  Iteratif untuk faktorial

Program :

//menghitung n! Menggunakan iteratif

//pre : n>=0

int factorial (int n){

int i; /*variabel lokal */

Product =1;

for (i=n; i>1; –i) {

product=product * i;

}

return(product);

}

 

9.1.3  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

2.     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)

9.2  Kasus Menara Hanoi

9.2.1 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


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s