Pemrograman Dasar LATIHAN METHOD / FUNGSI METHOD REKURSIF
Latihan 1 2 Buatlah program untuk menampilkan kuadrat dari suatu bilangan secara berulang sebanyak n kali 1. Buat method Header dengan tipe void (parameter judul bertipe String) ========================= PROGRAM KUADRAT BILANGAN ========================= 2. Buat method KuadratBilangan dengan tipe void (parameter n bertipe int) Contoh keluaran dengan input n = 10 : Kuadrat Kuadrat Kuadrat Kuadrat Kuadrat Kuadrat Kuadrat Kuadrat Kuadrat Kuadrat
dari dari dari dari dari dari dari dari dari dari
1 adalah 1 2 adalah 4 3 adalah 9 4 adalah 16 5 adalah 25 6 adalah 36 7 adalah 49 8 adalah 64 9 adalah 81 10 adalah 100
Latihan 2 3
Buatlah program untuk menghitung nilai rata-rata dari bilangan bertipe integer sebanyak n yang diinputkan oleh user 1. Buat method Header 2. Buat method Rata2Bilangan dengan tipe double (parameter banyaknya bilangan n bertipe integer) Contoh keluaran dengan input n = 4 : Masukkan bilangan 1 : 3 Masukkan bilangan 2 : 2 Masukkan bilangan 3 : 5 Masukkan bilangan 4 : 6 Rata-rata : 4.000
Method Rekursif 4
Method Rekursif
Method yang di dalamnya terdapat pernyataan yang memanggil dirinya sendiri
Berguna untuk memecahkan masalah yang dapat
didefinisikan secara rekursif pula. Contoh : Faktorial (n) atau n! didefinisikan sebagai berikut : jika n = 0, n! = 1 jika n > 0, n! = n * (n-1)!
Method Rekursif 5
Faktorial (n) atau n! didefinisikan sebagai berikut : jika n = 0, n! = 1 jika n > 0, n! = n * (n-1)! Misal n=4 : 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1* 0! 0! = 1 Jadi: 4! = 4*3*2*1= 24
Method Iteratif - Faktorial 6
4! = 4*3! = 4*3*2! = 4*3*2*1! = 4*3*2*1 = 24 decremental long faktorialIteratifDec(long n) { long i, faktorial = 1; for(i=n; i>=1; i--) faktorial *= i; return faktorial; }
4! = 1*2*3*4 = 24 incremental long faktorialIteratifInc(long n){ long i, faktorial = 1; for(i=1; i<=n; i++) faktorial *= i; return faktorial; }
Method Rekursif - Faktorial 7
Contoh perhitungan 5 faktorial 5! (5 * 4!) (5 * (4 *3!)) (5 * (4 * (3 * 2!))) (5 * (4 * (3 * (2 * 1!)))) (5 * (4 * (3 * (2 * (1 * 0!))))) (5 * (4 * (3 * (2 * (1 * 1))))) (5 * (4 * (3 * (2 * 1)))) (5 * (4 * (3 * 2))) (5 * (4 * 6 )) (5 * 24) 120
Method Rekursif 8
Fungsi rekursif mempunyai dua komponen yaitu:
Base case: Mengembalikan nilai tanpa melakukan pemanggilan rekursi berikutnya. Rekursi berakhir jika base case dijumpai/dipenuhi
Recursion call / Reduction step: Memanggil fungsi rekursif di dalam fungsi rekursif di atas Menghubungkan sebuah fungsi rekursif dengan fungsi rekursif di dalamnya
Biasanya memiliki keyword return untuk mengembalikan nilai ke fungsi yang memanggilnya
Method Rekursif 9
Fungsi faktorial Base case: n = 0 Reduction step: f(n) = n * f(n-1) // rekursif long faktorialRekursif(long n) { if(n==0) return (1); else return(n * faktorialRekursif(n-1)); }
Rekursif vs Iteratif 10 Faktorial - Rekursif long faktorial(long n) { if(n==0) return (1); else return(n*faktorial(n-1)); }
Faktorial - Iteratif // dekremental long faktorial(long n) { long i, faktorial = 1; for(i=n; i>=1; i--) faktorial *= i; return faktorial; }
Rekursif vs Iteratif 11
Rekursif 1.
2.
3.
4.
5.
Pengulangan dengan struktur seleksi (if-else) dan pemanggilan fungsi (dirinya sendiri) -> rekursi Pengulangan berhenti saat base case dijumpai/dipenuhi (konvergen terhadap base case) Pengulangan tanpa henti jika base case tidak pernah dijumpai/dipenuhi (tidak konvergen terhadap base case) Biaya proses lebih tinggi dengan pemanggilan banyak fungsi (butuh memori lebih besar & kerja prosesor lebih tinggi) Terbaca lebih jelas, model lebih dekat dengan masalah (contoh: faktorial, fibonacci)
Iteratif 1. 2. 3. 4.
5.
Pengulangan dengan struktur repetisi (for/while) Pengulangan berhenti saat kondisi pengulangan bernilai salah (false) Pengulangan tanpa henti jika kondisi pengulangan selalu benar Biaya proses lebih rendah (kebutuhan memori lebih kecil & kerja prosesor lebih rendah) karena proses pengulangan berada dalam satu fungsi Terbaca kurang jelas, model kurang dekat dengan masalah (contoh: faktorial, fibonacci)
Kekurangan Rekursif 12
Meskipun penulisan program dengan cara rekursif
bisa lebih jelas dan pendek, namun fungsi rekursif memerlukan :
Memori yang lebih banyak untuk mengaktifkan stack (memori yang digunakan untuk pemanggilan method).
Waktu lebih lama untuk menjejaki setiap rekursi melalui stack.
Apakah stack ?
Kapan menggunakan Rekursif ? 13
Secara umum, hanya jika : Penyelesaian sulit dilaksanakan secara iteratif Efisiensi dengan cara rekursif masih memadai Efisiensi bukan masalah dibandingkan dengan kejelasan logika program Tidak mempertimbangkan faktor penghematan memori dan kecepatan eksekusi program
Kecepatan kerja dan penghematan memori (iteratif) VS
Perancangan logika yang baik (rekursif)
Bilangan Fibonacci 14
Urutan bilangan 0, 1, 1, 2, 3, 5, 8, 13 … disebut
bilangan Fibonacci. Hubungan antara satu angka dengan angka berikutnya didefinisikan secara rekursif sebagai berikut :
Fib(N) = N, jika N = 0 atau 1
Fib(N) = Fib(N-2) + Fib(N-1) , jika N >= 2
Bilangan Fibonacci 15
int slow_Fib(int n) { int f; if(n==0) f = 0; else if(n==1) f = 1; else f = slow_Fib(n-2) + slow_Fib(n-1); return f; }
Method slow_Fib() di atas ditulis secara rekursif Tulislah fast_Fib() jika menggunakan iterasi.
Bilangan Fibonacci 16
Contoh : Skema fibonacci jika N=4
FIB (4)
FIB (3) FIB (2) FIB (1)
FIB (1)
FIB (0)
FIB (2) FIB (1)
FIB (0)
Tugas 1 17
Buatlah program untuk permasalahan bilangan
Fibonacci menggunakan iterasi int slow_Fib(int n) { int f; if(n==0) f = 0; else if(n==1) f = 1; else f = slow_Fib(n-2) + slow_Fib(n-1); return f; }
Tugas 2 18
Buatlah program untuk permasalahan perpangkatan
suatu bilangan menggunakan rekursif Contoh: 45
