Sabtu, 15 Januari 2011

STRUKTUR REKURSIF

Rekursif adalah suatu proses dari suatu subprogram yang dapat berupa fungsi atau prosedur yang memanggil dirinya sendiri.
Perulangan Rekursif dan Perulangan Iteratif.
Perulangan rekursif merupakan salah satu metode didalam pemrograman yang mana dalam sebuah fungsi terdapat intruksi yang memanggil fungsi itu sendri, atau lebih sering disebut memanggil dirinya sendiri.

Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok intruksi. Perulangan dilakukan dalam batasan syarat tertentu. Ketika syarat tersebut tidak terpenuhi lagi maka perulangan aka terhenti.

Persamaan :
1.Iteratif dan rekursif merupakan metode atau teknik didalam perulangan(looping)
2.Sama-sama memiliki bagian yang berfungsi sebagai batas dalam sebuah perulangan

Perbedaan :
Iteratif dalam melakukan perulangan membutuhkan suatu instruksi program seperti for, repeat until dan while do, sedangkan rekursi tidak memakai instruksi program seperti itu. Cukup dengan fungsi tersebut.

Procedure Rekursif;<--nama fungsi: rekursif. Begin Write(‘AMIK BSI ’); Rekursif;<--fungsi bernama rekursif ini dikatakan Sebagai fungsi rekursi karena dia memanggil Dirinya sendiri End; Begin Rekursif; End. Pada contoh diatas: sebuah fungsi/prosedur adalah sebuah proses. Contoh fungsi rekursif diatas adalah sebuah proses, dan didalam fungsi rekursif tersebut terdapat perintah/proses yang mengerjakan/memanggil proses rekursif (memanggil dirinya sendiri),sehingga fungsi/prosedur rekursif ini dinamakan fungsi rekursi. Pada contoh diatas proses rekursi ini tidak memiliki batas berhenti. Untuk mengetahui contoh fungsi rekursif ini silahkan melihat pada slide perkuliahan. Catatan: Fungsi/prosedur dalam sebuah bahasa pemrograman disebut juga subrutin/sub program. Subprogram ini berisi perintah –perintah khusus yang sering digunakan untuk proses pemrograman. Sehingga untuk menghindari penulisan kode program yang sering digunakan maka dibuatlah fungsi (subprogram). Cara untuk menggunakan subprogram yaitu dengan memanggil nama_fungsi tersebut melalui blok program utama. Contoh pemanggilan terdapat pada program faktorial. FUNGSI FAKTORIAL 0! = 1 N! = N x (N-1)! Untuk N > 0

function faktorial(N:integer):integer;
var i:integer;
begin
if N = 0 then
begin
faktorial :=1;
exit;
end
else
faktorial := n * faktorial(n-1);

end;

begin
write('Masukan Bilangan = '); readln(Bil);
write('jumlah faktorial = ',faktorial(Bil));
readln;
end.
HASIL:
Masukan Bilangan = 5
jumlah faktorial = 120

-->MENARA HANOI
Ini merupakan salah satu permasalahan rekursif yang terkenak dan pertama kali ditemukan oleh seorang pendeta Budha di Hanoi, Vietnam yang kemudian konsep tersebut dikenal dengan konsep menara Hanoi (The Tower of Hanoi). Menurut legenda pendeta tersebut akan memindahkan 64 buah piringan yang tidak sama besarnya dari satu menara ke menara lainnya.Mungkin karena terlalu sulit, pendet Budha tersebut mengatakan bahwa menara-menara tersebut berhasil dipindahkan.
Seperti permasalahan tersebut, bahwa permasalahan pada konsep ini adalah bagaimana cara memindahkan sejumlah piringan dari satu menara ke menara lainnya dengan satu menara bantu, dengan besar piringan tidak sama dan hanya boleh dilakukan hanya 1 kali.

Tujuan permainan ini adalah memindahkan n buah piringan dari tonggak asal A melalui tonggak bantu B menuju tonggak tujuan C. dengan aturan piring yang lebuh kecil tidak boleh berada dipiringan yang lebih besar.



Bayangkan keadaan berikut:
Ada 3 tiang (a, b, c) tempat piringan dengan ukuran yang bervariasi dapat ditumpuk. Pada mulanya semua piringan ada di “a”. Tugasnya adalah Memindah semua piringan ke “c” dengan aturan sbb:

• pada satu saat hanya boleh memindah 1 piringan
• setiap perpindahan berupa pengambilan piringan teratas dari satu tiang dan memasukannya ketiang lain, diatas piringan lain yang mungkin sudah ada pada tiang tersebut.
• Tidak boleh meletakan piringan diatas piringan lain yang lebih kecil. (piringan yang lebih besar tidak boleh berada di atas piringan yang lebih kecil).
• pada setiap akhir pemindahan semua piringan harus berada di tiang

Untuk Penyelesaian masalah kita daftarkan terlebih dahulu langkah-langkah penyelesaiannya:
a.ketika kondisi piringan  N= 1
Piringan 1 dipindahkan dari A ke C.
b.N =2
-->Pindahkan piringan 1 dari A ke B
-->Pindahkan piringan 2 dari A ke C
-->Pindahkan piringan 1 dari B ke C

Dari langkah – langkah penyelesaian diatas, maka dapat disimpulkan :
Untuk memindahkan piringan dari tonggak asal (A) ke tonggak tujuan (C) maka piringan ke N harus berada di tonggak tujuan (C).
Sedangkan piringan ke 1 sampai dengan (N-1) harus berada ditonggak bantu(B).
Setelah piringan ke 1 s/d N-1 berada di B, Kemudian pindahkan piringan ke 1 sampai dengan N-1 dari tonggak bantu (B) ke tonggak tujuan (C).


Untuk menyelesaikan masalah tersebut dapat digunakan algoritma Rekursif :

uses crt;
procedure Hanoi(n:integer;asal,bantu,tujuan:char);
begin
if n=0 then exit;
hanoi(n-1,asal,tujuan,bantu);
writeln('. Pindahkan piringan ke ',n,' dari ',asal,' ke ',tujuan);
hanoi(n-1,bantu,asal,tujuan);
end;

var N : integer;

begin
clrscr;
write('Jumlah Piringan = ');
readln(N);
hanoi(N,'A','B','C');
readln;
end.
Hasil :
Jumlah Piringan = 4
. Pindahkan piringan ke 1 dari A ke B
. Pindahkan piringan ke 2 dari A ke C
. Pindahkan piringan ke 1 dari B ke C
. Pindahkan piringan ke 3 dari A ke B
. Pindahkan piringan ke 1 dari C ke A
. Pindahkan piringan ke 2 dari C ke B
. Pindahkan piringan ke 1 dari A ke B
. Pindahkan piringan ke 4 dari A ke C
. Pindahkan piringan ke 1 dari B ke C
. Pindahkan piringan ke 2 dari B ke A
. Pindahkan piringan ke 1 dari C ke A
. Pindahkan piringan ke 3 dari B ke C
. Pindahkan piringan ke 1 dari A ke B
. Pindahkan piringan ke 2 dari A ke C
. Pindahkan piringan ke 1 dari B ke C

Hasil 2 :
Jumlah Piringan = 3
. Pindahkan piringan ke 1 dari A ke C
. Pindahkan piringan ke 2 dari A ke B
. Pindahkan piringan ke 1 dari C ke B
. Pindahkan piringan ke 3 dari A ke C
. Pindahkan piringan ke 1 dari B ke A
. Pindahkan piringan ke 2 dari B ke C
. Pindahkan piringan ke 1 dari A ke C

Referensi :
http://jkw1.wordpress.com/
http://yusriel.wordpress.com/
Yulikuspartono.2004.Pengantar Logika dan Algoritma,Yogyakarta.
Diposkan ole

Tidak ada komentar:

Posting Komentar