[2] Rekursi dan Looping
Fungsi Rekursif
Fungsi rekursif dalam pemrograman merupakan fungsi yang
memanggil/mendefinisikan dirinya sendiri selama kondisi
pemanggilan dipenuhi.
-- contoh kasus: perkalian 2 buah angka
Fungsi rekursif kali() untuk menghitung hasil kali dari dua bilangan:
public class FungsiRekursif {
public static void main(String[] args) {
//contoh perkalian
[Link]("2 x 4 = " + kali(2,4));
}
/*
fungsi rekursif yang menghitung hasil perkalian 2 buah angka
contoh: angka a dan b
diambil dari konsep matematka: perkalian merupakan penjumlahan berulang
*/
static int kali(int a, int b){
//if a dikalikan dengan angka 1
if(b==1)
return a;
//else
return a + kali(a, b - 1);
}
}
Mari kita uraikan langkah pemanggilannya:
kali(2, 4)
-> 2 + kali(2, 3)
-> 2 + (2 + kali(2, 2))
-> 2 + (2 + (2 + kali(2, 1)))
-> 2 + (2 + (2 + 2))
-> 2 + (2 + 4)
-> 2 + 6
-> 8
Komponen Fungsi Rekursif
1. Kondisi kapan berhentinya fungsi
ialah kondisi yang menyatakan kapan fungsi tersebut berhenti.
Kondisi ini harus dapat dibuktikan akan tercapai, jika tidak maka
fungsi tidak akan berhenti karena ada salah algoritma
2. Pengurangan atau pembagian data ketika fungsi memanggil dirinya sendiri
fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi
atau memecahkan data masukan setiap panggilannya. Hal ini
penting diingat, karena tujuan utama dari rekursif ialah
memecahkan masalah dengan mengurangi masalah tersebut
menjadi masalah-masalah kecil.
Apa bedanya rekursif dan iterasi/perulangan?
(catatan: looping/perulangan merupakan implementasi dari iterasi)
Pendekatan rekursif memecah-mecah masalah untuk kemudian
menyelesaikan masalah sedikit demi sedikit, dan
inputan/parameternya pasti berbeda ketika memanggil dirinya sendiri
lagi (lihat contoh program diatas)
Pendekatan iteratif justru langsung mencoba menyelesaikan masalah,
tanpa memecah-mecahkan masalah tersebut menjadi lebih kecil
terlebih dahulu
Kapan kita harus menggunakan rekursif?
Berikut ini beberapa contoh penggunaan algoritma rekursif:
menyelesaikan permasalahan di matematika,
- menghitung phi dengan membagi keliling lingkaran dengan
diameternya
- faktorial
penelurusan data di dalam sebuah binary tree.
sebuah binary tree, yang dapat didefinisikan sebagai sebuah pohon
dengan jumlah cabang yang selalu dua, secara alami adalah struktur
data rekursif.
Algoritma rekursif sangat tepat diterapkan untuk permasalahan yang
alaminya memang rekursif, seperti list dan pohon (tree), aplikasi games,
merge sort, dan quick sort. Tree akan kita pelajari dipraktikum
berikut-berikutnya :D
Looping
foreach
for-each merupakan salah satu perulangan di Java yang umumnya
digunakan untuk array atau class Collection di Java (ArrayList, dll).
sintaks for-each: setara dengan:
for (tipe_data var : array) { for (int i=0; I < [Link]; i++) {
//statements using var; tipe_data var = arr[i];
} //statements using var;
}
Hal yang kd bisa kita lakukan dengan for-each:
For-each loops are not appropriate when For-each loops do not keep track of index.
you want to modify the array So we can not obtain array index using
For-Each loop
for (int num : marks)
{ for (int num : numbers)
// only changes num, not the array {
element if (num == target)
num = num*2; {
} return ???; // do not know the
index of num
}
}
For-each only iterates forward over the For-each cannot process two decision
array in single steps making statements at once
// cannot be converted to a for-each loop // cannot be easily converted to a for-each
for (int i=[Link]-1; i>0; i--) loop
{ for (int i=0; i<[Link]; i++)
[Link](numbers[i]); {
} if (numbers[i] == arr[i])
{ ...
}
}
-- contoh kasus: mencari angka dengan nilai terbesar (maks) dalam array
class BelajarForeach{
public static void main(String[] arg){
{
int[] marks = { 125, 132, 95, 116, 110 };
int highest_marks = maximum(marks);
[Link]("Nilai tertinggi adalah " + highest_marks);
}
}
public static int maximum(int[] numbers){
int maxSoFar = numbers[0];
// for each loop
for (int num : numbers)
{
if (num > maxSoFar) {
maxSoFar = num;
}
}
return maxSoFar;
}
}