Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri, hingga pada batasan tertentu akan berhenti lalu mengolahnya dan pada akhirnya akan mengembalikan nilai.
Hampir semua kasus yang dapat diselesaikan dengan perulangan (for, while, do while, dll), juga dapat diimplementasikan menggunakan fungsi rekursif.
Menulis perulangan menggunakan fungsi rekursif, setidaknya membuat kode terlihat lebih sederhana. Namun, dengan implementasi yang salah, fungsi rekursif dapat berjalan dengan lambat seiring dengan bertambahnya data.
Code
Dibawah ini adalah fungsi max()untuk mencari angka paling besar dari sebuah array.
arr.slice(1, arr.length)→ Menghapus element pertama dari array, dan mengembalikan sisanya.
How it works
Setiap fungsi rekursif memiliki base case yang merupakan batasan fungsi tersebut untuk berhenti memanggil dirinya sendiri.
Base case pada kode diatas ditunjukkan pada baris ke-6
if (arr.length === 1) return arr[0];Base case ini akan melakukan pengecekan, apakah array hanya memiliki element 1? jika iya kembalikan element tersebut.
Jika tidak atau jika element array lebih dari 1, maka baris ke-6 akan dilewati, dan akan berlanjut ke baris ke-13
if (arr[0] > max(arr.slice(1, arr.length))) {
return arr[0];
}Pada baris ke-13 dilakukan pengecekan ulang:
Apakah element pertama dari array lebih besar dari hasil max(arr.slice(1, arr.length)) ?
Sampai disini kita akan menunggu hasil dari max(arr.slice(1, arr.length)), inilah kenapa fungsi ini disebut rekursif, karena pada pengecekan kedua ini memanggil dirinya sendiri max().
Jika yang dihasilkan lebih kecil dari element pertama array tadi, maka akan mengebalikan element pertama dari array.
Jika tidak, prosesnya akan dilanjutkan pada baris ke-20
else {
return max(arr.slice(1, arr.length));
}Pada kode ini menjelaskan bahwa selain kondisi tadi atau jika element pertama dari array tidak lebih besar dari hasil max(arr.slice(1, arr.length)), maka akan mengembalikan max(arr.slice(1, arr.length))
Pada pengecekan baris ke-20 ini akan memanggil dirinya sendiri max()
Case
Contoh kasus, ketika kita memasukkan array [1, 2, 3, 4]kedalam fungsi max()maka prosesnya
- Membandingkan element pertama dari array (
1) dengan nilai paling besar dari sisanya ([2, 3, 4]) - Menguraikan sisa dari array
[2, 3, 4]dengan membandingkan element pertama dari array2dengan nilai paling besar dari sisanya[3, 4] - Menguraikan sisa dari array
[3, 4]dengan membandingkan element pertama dari array3dengan nilai paling besar dari sisanya[4] - Ketika jumlah element dari array adalah 1, maka akan menyentuh base case yaitu akan mengembalikan nilai itu sendiri
4
Secara visual akan terlihat seperti dibawah ini
Meskipun kode diatas dapat dijalankan dengan baik, jika diperhatikan, kode tersebut memanggil frasa yang sama sebanyak dua kali max(arr.slice[1, arr.length]), sekali disetiap setengah dari pernyataan kondisionalnya.
Top-down
Kasus 1 — Array dengan 1 element
Ketika kita melempar array yang memiliki hanya satu element pada fungsi max(), katakanlah [4], maka fungsi max() akan mengembalikan element itu sendiri, yaitu 4
Hal ini dikarenakan kita menyentuh base case yang tertulis pada baris 6
if (arr.length === 1) return arr[0];Kasus 2 — Array dengan 2 element
Apa yang terjadi ketika kita memasukkan array yang memiliki 2 element pada fungsi max()? anggap saja [3, 4]
Pada kasus array dengan 2 element, maka komputer tidak akan mengeksekusi pengecekan pertama (base case) if (arr.length === 1) return arr[0]
Pada pengecekan kedua if(arr[0] > max(arr.slice(1, arr.length)) kita membandingkan 3 dengan hasil darimax([4]).
max([4]) adalah fungsi rekursif.
Karena 3 tidak lebih besar dari hasilnya, yaitu 4, maka akan memicu pengecekan kedua pada baris 21 yaitureturn max(arr.slice([1, arr.length])). Dalam hal ini mengembalikan max([4])
Sampai disini fungsi diatas sudah memanggil max([4]) sebanyak dua kali. Padahal ini array dengan 2 element, bagaimana jika array memiliki 5 element atau mungkin lebih?
Next step
Cara termudah untuk memperbaikinya adalah menyimpan panggilan rekursif ke dalam variabel.
Dengan melakukan perubahan tersebut, maka fungsi reskursif hanya dipanggil satu kali, dan meyimpan hasil nya pada satu variabel.
Jika digambarkan secara visual akan terlihat seperti dibawah ini
Dengan memindahkan fungsi rekursif ke dalam variabel, komputer sudah menghilangkan beberapa proses dilakukan berulang.
Efficiency
Pada fungsi yang pertama, akan memanggil dirinya sendiri sebanyak dua kali disetiap prosesnya (kecuali jika element dari array hanya berjumlah 1).
Pada tabel dibawah ini, kita akan melihat berapa jumlah panggilan yang dilakukan setiap kita menambahkan data yang akan di eksekusi.
Dengan melihat tabel di atas, dapat dilihat bahwa pada fungsi pertama memiliki notasi O(2ⁿ), dimana notasi ini memiliki arti bahwa fungsi tersebut sangat lambat seiring bertambahnya data yang dieksekusi.
Pada versi kedua, fungsi tersebut memanggil dirinya sendiri sebanyak jumlah element dari array yang diinputkan. Maka pada versi kedua, memiliki notasi O(N).
Seperti yang kita ketahui O(2ⁿ) lebih lambat dibanding O(N).
Wrapping up
Menghindari panggilan fungsi rekursif berlebihan adalah kunci untuk menjaga fungsi rekursif tetap cepat.
Meskipun perbaikan diatas terlihat sederhana yaitu memindahkan fungsi rekursif kedalam variabel. Pada akhirnya hal inilah yang mengubah kecepatan fungsi kita dari O(2ⁿ) menjadi O(N).
