PENDAHULUAN
Metode ITERATIF dan REKURSIF merupakan ke 2 cara dalam STRUKTUR DATA,yang mana merupakan solusi dalam membuat sebuah data didalam program computer sedikit mengupas Iteratif dan rekursif
Metode iteratif adalah suatu metode untuk menyelesaikan suatu sistem persamaan linear dengan cara tidak langsung. Metode iteratif dimulai dengan aproksimasi untuk solusi yang sebenarnya, dan bila konvergen, hasil aproksimasi terdekat dari barisan tersebut adalah siklus dari perhitungan-perhitungan yang diulang-ulang sampai ketelitian yang diinginkan.
Sedangkan Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri.
TEKNIK ITERATIF & REKURSIF
TEKNIK ITERATIF
Teknik Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan procedure beberapa kali atau hingga suatu kondisi tertentu terpenuhi
Contoh :
Teknik Iteratif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n, adalah sebagai berikut :
Function FAK (n : integer) : integer
FAK=1
For i = 1 TO n
FAK = FAK * i
NEXT i
END FAK
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka : FAK = 1, kemudian
i | FAK |
1 | 1 * 1 = 1 |
2 | 1 * 2 = 2 |
3 | 2 * 3 = 6 |
4 | 6 * 4 = 24 |
5 | 24 * 5 = 120 |
1. Set x, y, n, i, f : integer
2. x ← 1 ; y ← 1
3. If n 〉 2 then
begin
4. for i ← 3 to n do
begin
5. F ← x + y
6. x ← y
7. y ← F
end
else
8. F ← x
9. Write(F)
End
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
x=1, y=1, kemudian
i | F | x | y |
3 | 1 + 1 = 2 | 1 | 2 |
4 | 1 + 2 = 3 | 2 | 3 |
5 | 2 + 3 = 5 | 3 | 5 |
Function FAK (n : integer) : integer
1. If n := 0 then FAK := 1
2. Else FAK := n * FAK(n-1)
Contoh :
BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .
Teknik Rekursif pada algoritma untuk menentukan suku ke-n dari barisan bilangan Fibbonaci, adalah sebagai berikut :
Procedure F(n : integer) : integer
1. If n ≤ 2 then F(n) = 1
else F(n) = F(n-1) + F(n-2)
Endif
End
Perbedaan Antara Teknik Iteratif dan Rekursif :
ITERATIF | REKURSIF |
Tidak ada variabel lokal baru | Ada variabel lokal baru |
Program tidak sederhana | Program menjadi lebih sederhana |
PERMAINAN MENARA HANOI
Contoh paling umum dari penggunaan teknik rekursif adalah pada permainan menara Hanoi. Berdasarkan legenda, pertama kali dimainkan secara manual oleh seorang pendeta Budha di Hanoi, sehingga permainan ini disebut Menara Hanoi. Dalam permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satu tonggak ke tonggak lainnya, dengan diperbolehkan menggunakan (melewati) sebuah tonggak bantuan. Aturan permainannya adalah semua piringan pada tonggak A akan dipindahkan ke tonggak C (dapat dengan melewati tonggak bantuan B), dengan ketentuan bahwa pemindahan piringan dilakukan satu per satu dan piringan yang lebih besar tidak boleh diletakan di atas piringan yang lebih kecil.
Menurut legenda tersebut dikatakan bahwa jika anda selesai memindahkan seluruh 64 piringan, pada saat itu juga dunia kiamat. Ini menurut legenda, yang mungkin juga benar. Secara umum, untuk menyelesaikan n buah piringan diperlukan pemindahan sebanyak 2n –1 kali. Bayangkan jika untuk setiap pemindahan memerlukan waktu 1 detik, maka berapa waktu yang diperlukan untuk menyelesaikan 64 buah piringan.
Kompleksitas Waktu untuk Algoritma Rekursif
Bentuk rekursif :
- suatu subrutin/fungsi/ prosedur yang memanggil dirinya sendiri.
- Bentu dimana pemanggilan subrutin terdapat dalam body subrutin
- Dengan rekursi, program akan lebih mudah dilihat
Bentuk rekursi bertujuan untuk :
- menyederhanakan penulisan program
- menggantikan bentuk iterasi
Syarat bentuk rekursif:
- ada kondisi terminal (basis)
- subroutine call yang melibatkan parameter yang nilainya menuju kondisi terminal (recurrence)
Menghitung kompleksitas bentuk rekursif
Untuk bentuk rekursif, digunakan teknik perhitungan kompleksitas dengan relasi rekurens.
Contoh :
- Menghitung factorial
Function Faktorial (input n : integer) → integer {menghasilkan nilai n!, n tidak negatif} Algoritma If n=0 then Return Else Return n*faktorial (n-1) Endif |
Kompleksitas waktu :
- untuk kasus basis, tidak ada operasi perkalian → (0)
- untuk kasus rekurens, kompleksitas waktu diukur dari jumlah perkalian (1) ditambah kompleksitas waktu untuk faktorial (n-1)
Kompleksitas waktu :
T(n)=1+T(n-1)
=1+1+T(n-2)=2+T(n-2)
=2+1+T(n-3)=3+T(n-3)
=……………
=n+T(0)
= n + 0
Jadi T(n) = n
T(n)∈ O(n)
2. Menara Hanoi
→ Legenda di Hanoi, tentang kisah pendeta Budha bersama murid-muridnya.
Permasalahan :
Bagaimana memindahkan seluruh piringan tersebut ke sebuah tiang yang lain (dari A ke B); setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Ada tiang perantara C.
Kata pendeta, jika pemindahan berhasil dilakukan, maka DUNIA KIAMAT !!!
Procedure Hanoi (input n, A, B, C:integer) Algoritma If n=1 then Write (‘Pindahkan piringan dari’,A,’ke’,B) Else Hanoi(n-1,A,C,B) Writeln(‘Pindahkan piringan dari’,A,’ke’,B) Hanoi(n-1,C,B,A) Endif |
T(n)=2n-1 adalah jumlah seluruh perpindahan piringan dari satu tiang ke tiang lainnya.
Jika perpindahan 1 piringan butuh waktu 1 detik, maka waktu yang dibutuhkan :
2
= 10.446.744.073.709.551.615
= kira-kira 600 milyar tahun (???!!!)
3. Persoalan Minimum & Maksimum
procedure MinMaks2(input A : TabelInt, i, j : integer, output min, maks : integer) { Mencari nilai maksimum dan minimum di dalam tabel A yang berukuran n elemen secara Divide and Conquer. Masukan: tabel A yang sudah terdefinisi elemen-elemennya Keluaran: nilai maksimum dan nilai minimum tabel } Deklarasi min1, min2, maks1, maks2 : integer Algoritma: if i=j then { 1 elemen } min←Ai |
maks←Ai else if (i = j-1) then { 2 elemen } if Ai < Aj then maks←Aj min←Ai else maks←Ai fmin←Aj endif else { lebih dari 2 elemen } k←(i+j) div 2 { bagidua tabel pada posisi k } MinMaks2(A, i, k, min1, maks1) MinMaks2(A, k+1, j, min2, maks2) if min1 < min2 then min←min1 else min←min2 endif if maks1<maks2 then maks←maks2 else maks←maks2 endif Relasi rekurrens: T(n)= Penyelesaian: Asumsi: n = 2k, dengan k bilangan bulat positif, maka T(n) = 2T(n/2) + 2 = 2(2T(n/4) + 2) + 2 = 4T(n/4) + 4 + 2 = 4T(2T(n/8) + 2) + 4 + 2 = 8T(n/8) + 8 + 4 + 2 = ... = = Jadi T(n)=3n/2 T(n)E0(n) ALGORITMA REKURSIF Terdapat lebih dari satu cara untuk mengimplementasikan struktur perulangan (iterasi) dalam Bahasa C, yaitu menggunakan statement for, menggunakan statement while atau menggunakan statement do/while. Selain dengan metoda iterasi, perulangan juga bisa dilakukan secara rekursif. Artinya, perulangan dilakukan melalui "pemanggilan sebuah fungsi oleh dirinya sendiri". Prosedur atau fungsi yang memanggil dirinya sendiri, baik secara langsung maupun tidak langsung, disebut sebagai prosedur rekursif atau fungsi rekursif [DEI02]. Fungsi Rekursif Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Fungsi ini akan terus berjalan sampai kondisi berhenti terpenuhi, oleh karena itu dalam sebuah fungsi rekursif perlu terdapat 2 blok penting, yaitu blok yang menjadi titik berhenti dari sebuah proses rekursi dan blok yang memanggil dirinya sendiri. Contoh – contoh penerapan rekursif: 1. Fungsi cetak ke layar Fungsi ini mencetak nilai dari paremeter yang dilempar kepadanya. Jika nilai dari parameter tersebut > 0, fungsi akan mencetak nilai dari parameter tersebut dan kemudian memanggil dirinya lagi, jika tidak, program berhenti. Faktorial dapat dibuat dengan menerapkan rekursi. Berikut ini adalah fungsi faktorial rekursif dari sebuah program Untuk melihat lebih jelas, terapkan fungsi di atas dalam sebuah program. 2. Fungsi pangkat Fungsi ini digunakan untuk menghitung nilai: Xn dengan n berupa bilangan bulat positif. Solusi dari persoalan ini: JIKA n = 1 MAKA Xn = X SELAIN ITU: Xn = X * Xn-1 Sebagai contoh diambil nilai X=5 dengan n=3, pelukisan proses pemecahannya: Berikut adalah fungsi pangkat dengan menggunakan solusi di atas: a adalah bilangan yang dipangkatkan, sedangkan b adalah bilangan pemangkatnya. Jika nilai dari b adalah 1, return a, lainnya return a dikali dengan fungsi pangkat dengan parameter a dan b-1. Untuk lebih jelas, terapkan dalam program. 3. Fungsi faktorial Fungsi rekursif dapat digunakan untuk menghitung faktorial. Berikut penjelasan beserta dengan contoh listing programnya. Fungsi faktorial dapat dinyatakan dalam bentuk rekursif seperti berikut: fak(n) = 1, untuk n = 0 atau n = 1 fak(n) = n x (n-1)!, untuk n > 0 Berikut contoh proses untuk perolehan hasil 4! ARRAY Array adalah sekelompok data sejenis yang disimpan ke dalam variabel dengan nama yang sama, dengan memberi indeks pada variabel untuk membedakan antara yang satu dengan yang lain. VARIABEL ARRAY nama_variabel[indeks] ketentuan nama variabel arrray sama dengan nama variabel biasa. indeks menunjukkan nomor dari variabel . DEKLARASI VARIABEL ARRAY BU : tipe nama_variabel[indeks]; Contoh : float bil[10]; deklarasi variabel array dengan nama bil yang akan menampung 10 data yang bertipe float. Indeks 10 menunjukkan variabel bil terdiri dari 10 elemen, dimana setiap elemen akan menampung sebuah data. Indeks array dimulai dari nol(0) , sedang nomor elemen biasanya dimulai dari satu(1). Nomor elemen dapat dibuat sama dengan nomor indeks untuk mempermudah pembuatan program yaitu dengan memberi indeks satu lebih banyak dari jumlah data yang dibutuhkan, sehingga menjadi : float bil[11] INISIALISASI ARRAY 1 DIMENSI Inisialisasi dapat dilakukan bersama dengan deklarasi atau tersendiri. Inisialisasi suatu array adalah dengan meletakkan elemen array di antara tanda kurung kurawal {}, antara elemen yang satu dengan lainnya dipisahkan koma. int bil[2] = {4,1,8} bil[0] = 4 bil[1] = 1 bil[2] = 8 AUTOMATIC ARRAY adalah Inisialisasi array dilakukan di dalam fungsi tertentu. Hanya compiler C yang berstandar ANSI C yang dapat menginisialisasikan automatic array. Cara menginisialisasikan array dari compiler yg tidak mengikuti standar ANSI C: 1. Diinisialisasikan di luar fungsi sebagai variabel GLOBAL/EXTERNAL ARRAY. int bil[2]={0,0,0}; main() 2. Diinisialisasikan didlm fungsi sebagai variabel LOKAL/STATIC ARRAY. main() { static int bil[2]={0,0,0}; ......... Pada automatic array yang tidak diinisialisasikan , elemen array akan memiliki nilai yang tidak beraturan. Bila global & static array tidak diinisialisasi maka semua elemen array secara otomatis akan diberi nilai nol(0). Contoh : main() { int y; int hitung=0; int x[0]; for(y=0;y<5;y++) { hitung+=y; x[y]=hitung; printf("%3d - %3d\n",y,x[y]); } } OUTPUT: 0- 0 1- 1 2- 3 3- 6 4- 10 MENDEFINISIKAN JUMLAH ELEMEN ARRAY DALAM VARIABEL Besarnya variabel indeks dapat ditentukan dengan menggunakan preprocessor directives #define #define N 40 main() { int no[N],gaji[N],gol[N],status[N],juman[N]; Bila besari indeks akan diubah menjadi 50, cukup diganti dengan #define N 50 ARRAY 2 DIMENSI nama_variabel [indeks1][indeks2] indeks1 : jumlah/nomor baris indeks2 : jumlah/nomor kolom Jumlah elemen yang dimiliki array 2 dimensi dapat ditentukan dari hasil perkalian indeks1 * indeks2 misal : array A[2][3] akan memiliki 2*3 = 6 elemen. main() { float bil [5] [5] ....... dapat dituliskan dengan #define #define N 5 main() { float bil [N] [N] ....... INISIALISASI ARRAY 2 DIMENSI main() { float bil[2] [3] = { { 1,2,3}, /*baris 0*/ { 4,5,6}, /*baris 1*/ } elemen bil [0] [0] = 1 elemen bil [0] [1] = 2 elemen bil [0] [2] = 3 elemen bil [1] [0] = 4 elemen bil [1] [1] = 5 elemen bil [1] [2] = 6 Contoh : main() { int x[3][5]; int y,z; int hitung=0; for(y=0;y<3;y++) { printf("y = %d\n",y); for(z=0;z<5;z++) { hitung+=z; x[y][z] = hitung; printf("%/t%3d - %3d\n",z,x[y][z]); } } } OUTPUT: y = 0 0- 0 1- 1 2- 2 3- 6 4- 10 y = 1 0- 10 1- 11 2- 13 3- 16 4- 20 y = 2 0- 20 1- 21 2- 23 3- 26 4- 30 STRING dan ARRAY 1. Pada string terdapat karakter null(\0) di akhir string 2. String sudah pasti array, array belum tentu string PENUTUP Iteratif dan rekursif merupakan metode atau teknik didalam perulangan(looping),dan Sama-sama memiliki bagian yang berfungsi sebagai batas dalam sebuah perulangan Demikianlah beberapa sekumpulan mengenai Iteraktif dan Rekursif,Sebenarnya untuk Rekursif dan Iteraktif ini sendiri masihlah belum semuanya dibahas di dalam makalah ini,dikarenakan keterbatasan nara sumber dan juga ilmu pengetahuan yang ada Akhir dari kata Saya ucapkan terima kasih. DAFTAR PUSTAKA [DEI02] Deitel & Deitel. 2002. Java : How To Program. 4th Ed. Prentince-Hall. GOO5] Goodrich & Tamassia. 2005. Data Structures and Algorithm in Java. 5th Ed. John Wiley & Sons. [LYS03] L. Yohannes Stefanus. 2003. Soal UTS Kelas Matrikulasi, Program Magister Teknologi Informasi, Universitas Indonesia. Tidak dipublikasikan. [RIN05] Rinaldi Munir. 2005. Algoritma dan Pemrograman dengan Bahasa Pascal dan C. Edisi 3. Buku 2. Bandung: Informatika Dari Situs Internet google tentang ITERAKTIF DAN REKURSIF |
