PEMROGRAMAN DASAR Sistem Informasi PTIIK UB Semester Ganjil 2014/2015
Fungsi Rekursif
Dr. Eng. Herman Tolle, ST., MT Program Teknologi Informasi & Ilmu Komputer, Universitas Brawijaya
“Fungsi yang memanggil dirinya sendiri”
FUNGSI REKURSIF
REKURSIF • Rekursif merupakan salah satu metode dalam dunia matematika dimana definisi sebuah fungsi mengandung fungsi itu sendiri. • Dalam dunia pemrograman, rekursif diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri dan tergolong dalam dynamic programming.
FUNGSI REKURSIF • Metoda rekursif adalah metoda yang memanggil dirinya sendiri. • Digunakan pada fungsi yang dapat dieksekusi secara iteratif (berulang) • Metoda ini memanggil dirinya sendiri sehingga dapat melakukan proses berulang-ulang. • Kasus sederhana yang sering muncul adalah proses berulang-ulang menghitung hasil faktorial. • 0! = 1; n! = n × (n – 1)!, n> 0!
• Faktorial dari 5 adalah 1 x 2 x 3 x 4 x 5. • Dari proses itu kita ketahui bahwa untuk menghitung factorial 5 manualnya seperti 1 x 2 = 2, lalu hasil 2 ini dikalikan 3 sehingga hasilnya adalah 6, lalu hasil 6 ini dikalikan lagi dengan 4 sehingga hasilnya adalah 36, lalu hasil 36 ini dikalikan dengan 5 sehingga hasilnya adalah 120. • 0! = 1; n! = n × (n – 1)!, n> 0!
Contoh class faktorialDemo{ public static void main(String args[]){ System.out.println("Hitung Faktorial dengan Rekursif"); System.out.println("Faktorial dari 4 adalah : "+ fak_rekursif(4)); System.out.println("Hitung Faktorial dengan Perulangan"); System.out.println("Faktorial dari 4 adalah : "+ fak_perulangan(4)); } }
private static int fak_perulangan(int n) { int t; int Hasil; Hasil = 1; for(t=1; t<=n; t++) Hasil *= t; return Hasil; }
private static int fak_rekursif(int n) { int Hasil; if(n==1 || n==0) return 1; Hasil = fak_rekursif(n-1) * n; return Hasil; }
Case: Deret Fibonaci Deret : 0 1 1 2 3 5 8 13 21 34 55 89 ... indeks: 0 1 2 3 4 5 6 7 8 9 10 11 • Deret Fibonacci dimulai dengan 0 dan 1, dan hasil penjumlahan dua nilai deret sebelumnya menjadi nilai indeks yang berikut. • Deret ini dapat didefinisikan rekursif sebagai berikut: fib(0) = 0; fib(1) = 1; fib(index) = fib(index-2) + fib(index-1);
utk index >= 2
Latihan • Buat algoritma dan kode program fungsi rekursif untuk perhitungan x pangkat y • Contoh: – Input : x,y – Proses: x^y = 1, jika y = 0 – x^y = x * x^(y-1), jika y > 0
class Pangkat { public static int pangkatRekursif(int x, int y) { if (y == 0) { return 1; } else { return x * pangkatRekursif(x, y - 1); } } public static void main(String[] args) { int A = pangkatRekursif(10,3) System.out.println("10 dipangkatkan 3 = “ + A); } }
Contoh Penerapan Fungsi Rekursif • Faktorial • Fraktal • Tree • Faktor Persekutuan Terbesar (Greatest Common Divisor (GCD)) • Algoritma Rekursif Best First Searching (RBFS)
Fraktal, Tree
Greatest Common Divisor (GCD) • FPB (Faktor Persekutuan Terbesar) dalam bahasa inggris dinamakan Greatest Common Divisor (GCD). • FPB dari dua bilangan adalah bilangan bulat positif terbesar yang membagi habis kedua bilangan. Bilangan yang dibandingkan tersebut berupa bilangan bulat atau integer. • Dalam definisi tersebut yaitu membagi habis kedua bilangan bulat positif, berarti harus dihitung modulo-nya (sisa hasil bagi dari kedua bilangan).
• FPB x dan y memiliki pola sebagai berikut: • Jika x dibagi y sama dengan 0, maka FPB dari x dan y adalah y • Jika x dibagi y tidak sama dengan 0, maka y dibagi dengan sisa pembagian x dan y • Formulanya adalah: • x % y = 0, FPB x dan y adalah y • x % y != 0 , maka y dibagi dengan hasil dari (x % y)
Fungsi GCD non rekursif /** Memberikan nilai balik gcd atas input dua integer */ public static int gcd(int n1, int n2) { int gcd = 1; // gcd awal = 1 int k = 2; // gcd yang mungkin while (k <= n1 && k <= n2) { if (n1 % k == 0 && n2 % k == 0) gcd = k; // Perbarui gcd k++; } return gcd; // Memberikan nilai balik gcd }
Fungsi Rekursif GCD public class Euclid { // implementasi recursive public static int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); } public static void main(String[] args) { int p = Integer.parseInt(args[0]); // baca input argumen 0 int q = Integer.parseInt(args[1]); // baca input argumen 1 int d = gcd(p, q); System.out.println("gcd(" + p + ", " + q + ") = " + d); } }
Pemanggilan: C:\Code>javac Euclid 1440 408 Hasil eksekusi: gcd(1440, 408) = 24
Proses dlm program: gcd(1440, 408) gcd(408, 216) gcd(216, 192) gcd(192, 24) gcd(24, 0) return 24 return 24 return 24 return 24 return 24
