Rekursi adalah konsep dalam pemrograman, di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil dari masalah awal hingga mencapai kondisi dasar.
Kondisi dasar ini adalah titik di mana rekursi berhenti, dan solusi akhir dikembalikan. Dalam pemrograman, konsep ini sangat berguna untuk memecahkan masalah yang dapat dibagi menjadi submasalah yang lebih sederhana dengan pola yang sama.
Baca juga: Apa Itu Coding? Begini Definisi, Tipe Bahasa, dan Arti Pentingnya
Fungsi Rekursi
Fungsi rekursi adalah fungsi yang secara eksplisit memanggil dirinya sendiri di dalam definisinya. Kunci utama dari hal ini adalah adanya basis kasus (base case) yang menentukan kapan fungsi harus berhenti memanggil dirinya sendiri.
Tanpa basis kasus, sebuah fungsi rekursi akan terus memanggil dirinya tanpa henti dan menyebabkan stack overflow, yang bisa menghabiskan memori komputer.
Keuntungan utama dalam menggunakan konsep ini adalah kemampuannya untuk menyederhanakan masalah kompleks, terutama ketika masalah tersebut melibatkan struktur data yang berulang seperti pohon, grafik, atau masalah pembagian dan penaklukan (divide and conquer).
Fungsi rekursi biasanya jauh lebih elegan dan mudah dibaca dibandingkan dengan solusi iteratif yang memerlukan pengulangan melalui loop.
Namun, terdapat pula beberapa kelemahannya, seperti penggunaan memori yang lebih banyak dibandingkan dengan iterasi, karena setiap pemanggilan fungsi memerlukan tempat penyimpanan di memori.
Untuk masalah sederhana, pendekatan iteratif mungkin lebih efisien daripada rekursi.
Baca juga: Apa Itu Programmer? Pengertian, Tugas, Jenis, Skill, dan Cara Menjadi Programmer
Contoh Rekursi dalam Pemrograman
Berikut adalah beberapa contoh penerapan rekursi dalam pemrograman.
Faktorial
Faktorial adalah salah satu contoh rekursi paling dasar dan sering digunakan dalam pemrograman. Faktorial dari sebuah angka nnn, ditulis sebagai n!n!n!, adalah hasil perkalian semua bilangan bulat positif dari 1 hingga nnn. Dalam rekursi, faktorial dapat didefinisikan sebagai:
python
Copy code
def faktorial(n):
if n == 0:
return 1
else:
return n * faktorial(n-1)
Dalam kode ini, basis kasusnya adalah ketika nnn sama dengan 0, di mana fungsi akan mengembalikan 1. Jika tidak, fungsi akan memanggil dirinya sendiri dengan parameter n−1n-1n−1, dan terus berulang sampai mencapai basis kasus.
Deret Fibonacci
Deret Fibonacci adalah contoh lain yang sering menggunakan rekursi dalam informatika.
Deret ini dimulai dengan dua angka pertama, yaitu 0 dan 1, dan setiap angka berikutnya adalah hasil penjumlahan dua angka sebelumnya. Dalam konsep ini, deret Fibonacci dapat dituliskan sebagai:
python
Copy code
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
Pada contoh ini, terdapat dua basis kasus, yaitu ketika nnn bernilai 0 dan 1. Untuk nilai lainnya, fungsi memanggil dirinya sendiri dua kali dengan parameter n−1n-1n−1 dan n−2n-2n−2, yang secara bertahap menghitung nilai deret Fibonacci.
Pencarian Biner (Binary Search)
Proses rekursi juga sering digunakan dalam algoritma divide and conquer seperti pencarian biner.
Dalam pencarian biner, data yang diurutkan dibagi dua, dan jika nilai yang dicari tidak ditemukan di tengah, maka pencarian dilanjutkan pada setengah bagian yang sesuai.
python
Copy code
def binary_search(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)
Basis kasusnya adalah ketika indeks low lebih besar dari high, yang berarti nilai yang dicari tidak ada dalam array.
Baca juga: Apa Itu Refactoring? Manfaat, Contoh, dan Cara Melakukannya
Kesimpulan
Rekursi adalah konsep penting dalam pemrograman yang membantu menyelesaikan masalah yang dapat dibagi menjadi submasalah yang lebih kecil.
Dengan mendefinisikan fungsi yang memanggil dirinya sendiri, konsep ini akan mempermudah programmer untuk menangani masalah kompleks seperti faktorial, deret Fibonacci, atau pencarian biner.
Namun, penting untuk selalu memastikan adanya basis kasus dalam setiap fungsi rekursi, agar proses dapat berhenti dan tidak menyebabkan kesalahan memori.
Meskipun memiliki beberapa kelemahan, terutama terkait penggunaan memori, dalam situasi yang tepat, tetapi konsep ini menawarkan solusi yang lebih elegan dan efisien.