ALGORITHM
3
Rekursif Algorithm Dahlia Widhyaestoeti, S.Kom
[email protected] dahlia74march.wordpress.com
Rekursif adalah salah satu metode dalam dunia matematika dimana definisi sebuah fungsi mengandung fungsi itu sendiri. Dalam dunia pemrograman, rekursi diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri
Contoh fungsi rekursif misalnya adalah fungsi pangkat, faktorial, dan barisan fibonacci.
Fungsi Pangkat Dalam fungsi pangkat xy , kita tahu bahwa semua bilangan selain 0, jika dipangkatkan dengan 0 nilainya sama dengan 1. Jika x dipangkatkan dengan y, dengan y lebih dari 0, maka hasilnya sama dengan x dikalikan dengan x dipangkatkan y – 1.
Fungsi Pangkat Jika dituliskan dalam notasi matematika definisinya adalah sebagai berikut:
y
X = 1, Jika y = 0 y
X =XxX
y-1
, jika y > 0
Kita lihat di atas pada definisi y > 0, bentuk pemangkatan muncul kembali di sisi kanan. Itulah yang disebut rekursif.
Fungsi Pangkat Definisi rekursif selalu dimulai dengan kasus penyetop, penghenti, atau kasus dasar dari suatu permasalahan, dalam hal ini terjadi ketika nilai y = 0. Definisi rekursif yang lebih kompleks mengandung inti dari permasalahan yang akan dipecahkan, namun lebih sederhana. Dalam hal ini yang tadinya x dipangkatkan dengan y, kini bentuk pemangkatan menjadi lebih sederhana, yaitu y – 1. Hal ini dimaksudkan untuk “menggiring” masalah kompleks ke kasus dasar atau penyetop rekursinya.
Fungsi Pangkat Untuk x = 10 dan y = 0, hasil dari xy adalah 1. Untuk x = 10 dan y = 3, hasilnya dapat digambarkan sebagai berikut:
Contoh Lain
Fungsi Pangkat Mari kita lihat contoh rekursif yang jauh lebih sederhana, Masalah yang akan dipecahkan adalah memotong roti tawar tipis-tipis sampai habis. Jika masalah ini akan dipecahkan secara rekursif, maka solusinya adalah:
1. Jika roti sudah habis atau potongannya sudah paling tipis, pemotongan roti selesai 2. Jika roti masih bisa dipotong, potong tipis dari tepi roti tersebut, lalu lakukan prosedur 1 dan 2 untuk sisa potongannya.
Contoh Program
Faktorial
program faktorial; uses wincrt; var faktor :real; i,n :integer; begin write('Masukkan bilangan n =');readln(n); faktor:=1; for i:= 2 to n do {Menghitung n faktorial} faktor:=faktor*i; writeln(n,' Faktorial = ',faktor:0:0); end.
Hasil Program
Faktorial
Masukan Bilangan n = 3 3 Faktorial 6 Masukan Bilangan n = 2 2 Faktorial 1
Faktorial Fungsi menghitung bilangan Faktorial dengan cara rekursif :
0! = 1 N! = N x (N-1)! Untuk N>0 Buatlah flowchart untuk fungsi faktorial berikut : Definisikan N adalah jumlah bilangan yang akan diinputkan Jika N = 0 maka variabel Faktorial = 1 Jika N ≠ 0 , maka variabel Faktorial = N * Faktorial(N-1)
Ilustrasi Fungsi Faktorial dengan proses rekursif :
Faktorial
Faktorial(6) = 6 * Faktorial(5) Faktorial(5) = 5 * Faktorial(4) Faktorial(4) = 4 * Faktorial(3) Faktorial(3) = 3 * Faktorial(2) Faktorial(2) = 2 * Faktorial(1) Faktorial(1) = 1 * Faktorial(0) Nilai Awal
Barisan Fibonacci Bilangan Fibonacci bisa didefinisikan berdasar deret integer tak terhingga sebagai berikut : 1 1 2 3 5 8 12
13
21
34
55
89 ...
Dari deret diatas bisa dilihat bahwa bilangan ke N (N>2) dalam deret bisa dicari dari 2(dua) bilangan sebelumnya yang terdekat dengan bilangan ke Nm yaitu bilangan ke (N-1) dan bilangan ke (N-2). Sehingga jika FIBO(N) menunjukan bilangan Fibonacci suku ke N, maka FIBO(N) bisa dihitung berdasar hubungan rekurens :
FIBO(N) = FIBO(N-1) + FIBO(N-2)
Ilustrasi Fungsi FIBO dengan proses rekursif :
Barisan Fibonacci
Karena FIBO(N) ditentukan oleh 2 nilai yang berbeda dengan argumen yang lebih kecil, maka untuk mencari bilangan Fibonacci diperlukan 2 nilai awal, yaitu : FIBO(1) = 1 dan FIBO(2) – 2.
FIBO(6) = FIBO(5) + FIBO(4) FIBO(5) = FIBO(4) + FIBO(3) FIBO(4) = FIBO(3) + FIBO(2) Nilai Awal FIBO(3) = FIBO(2) + FIBO(1) Nilai Awal Nilai Awal
Menyusun Permutasi Contoh lain dari proses rekursif adalah menyusun semua permutasi yang mungkin dari sekelompok karakter. Contoh : Jika kita mempunyai 3 buah karakter A, B dan C, maka semua permutasi yang mungkin dari ketiga karakter tersebut adalah :
A A B B C C
B C A C A B
C B C A B A
Secara umum, banyaknya permutasi dari N buah karakter adalah N Faktorial. Dalam contoh tersebut N = 3, sehingga banyaknya permutasi adalah 3! = 6
Menyusun Permutasi Proses penyusunan permutasinya bisa dijelaskan berikut : ➔ Cetak elemen ke-1, dan cetak permutasi elemen ke-2 sampai ke N
(permutasi dengan N-1 elemen). ➔ Cetak elemen ke-2, dan cetak permutasi elemen ke-1, elemen ke 3 sampai ke N(permutasi dengan N-1 elemen). ➔ Cetak elemen ke-3, dan cetak permutasi elemen ke-1, elemen ke-2, elemen ke-4 sampai ke N(permutasi dengan N-1 elemen). ➔ Dan seterusnya, sampai langkah terakhir adalah cetak elemen ke N, dan cetak permutasi elemen ke 1 sampai elemen ke (N-1) (permutasi dengan N-1 elemen).
Contoh N = 3, maka : ➔ Cetak 'A' dan cetak permutasi ('B' , 'C') ➔ Cetak 'B' dan cetak permutasi ('A' , 'C') ➔ Cetak 'C' dan cetak permutasi ('A' , 'B')
Legenda Menara Hanoi (oleh Edouard Lucas abad 19) • • • •
Seorang biarawan memiliki 3 menara. Diharuskan memindahkan 64 piringan emas. Diameter piringan tersebut tersusun dari ukuran kecil ke besar. Biarawan berusaha memindahkan semua piringan dari menara pertama ke menara ketiga tetapi harus melalui menara kedua sebagai menara tampungan. Kondisi:
• •
Piringan tersebut hanya bisa dipindahkan satu-satu. Piringan yang besar tidak bisa diletakkan di atas piringan yang lebih kecil.
Ternyata : mungkin akan memakan waktu sangat lama (sampai dunia kiamat). Secara teori, diperlukan 264-1 perpindahan. Jika kita salah memindahkan, maka jumlah perpindahan akan lebih banyak lagi. Jika satu perpindahan butuh 1 detik, maka total waktu yang dibutuhkan lebih dari 500 juta tahun !!.
Menara Hanoi
Menara Hanoi
Menara Hanoi
Untuk memindahkan n piringan dari tiang 1 ke tiang 3: 1. Pindahkan (n-1) piringan dari tiang 1 ke tiang 2 2. Pindahkan 1 piringan (terbesar) dari tiang 1 ke tian 3 3. Pindahkan (n-1) piringan dari tiang 2 ke tiang 3
H(n) : untuk memindahkan n piringan 1. H(n-1) pemindahan 2. 1 pemindahan 3. H(n-1) pemindahan
total ada 2H(n-1) + 1
Menara Hanoi Rumus : H(n) = 2 H(n – 1) + 1 Algoritma:
Jika
n==1, pindahkan pringan dari A ke C Jika tidak: Pindahkan n-1 piringan dari A ke B menggunakan C sebagai tampungan Pindahkan n-1 piringan dari B ke C menggunakan A sebagai tampungan
