Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan suatu masalah. Algoritma rekursif memecah masalah menjadi sub-masalah yang lebih kecil dan menyelesaikannya satu per satu. Pada bab ini, kita akan membahas konsep dasar rekursi, cara kerjanya, dan beberapa contoh algoritma rekursif klasik.
6.1 Konsep Dasar Rekursi
Rekursi memerlukan dua komponen utama:
- Kasus Dasar (Base Case): Kondisi yang menghentikan rekursi. Ketika kasus dasar terpenuhi, fungsi tidak memanggil dirinya sendiri lagi.
- Kasus Rekursif (Recursive Case): Kondisi di mana fungsi memanggil dirinya sendiri dengan argumen yang dimodifikasi untuk mendekati kasus dasar.
Contoh Rekursi Sederhana: Faktorial
Faktorial dari suatu bilangan n (ditulis sebagai n!) adalah hasil perkalian semua bilangan bulat positif kurang dari atau sama dengan n.
Definisi faktorial secara rekursif:
- Kasus dasar: 0! = 1
- Kasus rekursif: n! = n * (n - 1)!
Implementasi Faktorial dalam Python
def faktorial(n):
if n == 0:
return 1
else:
return n * faktorial(n - 1)
# Contoh penggunaan
print(faktorial(5)) # Output: 120
Dalam contoh ini, faktorial(5) memanggil faktorial(4), yang pada gilirannya memanggil faktorial(3), dan seterusnya, hingga mencapai kasus dasar faktorial(0).
6.2 Algoritma Rekursif Klasik
Mari kita bahas beberapa algoritma rekursif klasik yang sering digunakan dalam pemrograman.
6.2.1 Deret Fibonacci
Deret Fibonacci adalah deret angka di mana setiap angka adalah jumlah dari dua angka sebelumnya. Definisi rekursif dari deret Fibonacci:
- Kasus dasar: F(0) = 0, F(1) = 1
- Kasus rekursif: F(n) = F(n - 1) + F(n - 2)
Implementasi Deret Fibonacci dalam Python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# Contoh penggunaan
print(fibonacci(6)) # Output: 8
6.2.2 Pencarian Biner Rekursif
Pencarian biner adalah metode pencarian yang efisien untuk menemukan elemen dalam daftar yang sudah terurut. Algoritma ini bekerja dengan membagi daftar menjadi dua bagian dan mencari di salah satu bagian tersebut.
Implementasi Pencarian Biner Rekursif dalam Python
def pencarian_biner_rekursif(arr, x, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return pencarian_biner_rekursif(arr, x, low, mid - 1)
else:
return pencarian_biner_rekursif(arr, x, mid + 1, high)
# Contoh penggunaan
arr = [2, 3, 4, 10, 40]
x = 10
result = pencarian_biner_rekursif(arr, x, 0, len(arr) - 1)
print(f'Elemen ditemukan pada indeks: {result}') # Output: Elemen ditemukan pada indeks: 3
6.3 Masalah Pembagian dan Penaklukan (Divide and Conquer)
Algoritma rekursif sering digunakan dalam pendekatan pembagian dan penaklukan, di mana masalah dipecah menjadi sub-masalah yang lebih kecil, diselesaikan secara rekursif, dan digabungkan kembali untuk menghasilkan solusi akhir.
6.3.1 Merge Sort
Merge Sort adalah algoritma pengurutan yang menggunakan pendekatan pembagian dan penaklukan. Algoritma ini membagi array menjadi dua bagian, mengurutkan kedua bagian tersebut secara rekursif, dan kemudian menggabungkan kedua bagian yang sudah terurut.
Implementasi Merge Sort dalam Python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
kiri = arr[:mid]
kanan = arr[mid:]
merge_sort(kiri)
merge_sort(kanan)
i = j = k = 0
while i < len(kiri) and j < len(kanan):
if kiri[i] < kanan[j]:
arr[k] = kiri[i]
i += 1
else:
arr[k] = kanan[j]
j += 1
k += 1
while i < len(kiri):
arr[k] = kiri[i]
i += 1
k += 1
while j < len(kanan):
arr[k] = kanan[j]
j += 1
k += 1
return arr
# Contoh penggunaan
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("Array terurut:", sorted_arr) # Output: Array terurut: [5, 6, 7, 11, 12, 13]
6.4 Tail Recursion
Tail recursion adalah bentuk khusus dari rekursi di mana panggilan rekursif adalah operasi terakhir dalam fungsi. Banyak bahasa pemrograman dapat mengoptimalkan tail recursion untuk menghindari penggunaan stack yang berlebihan dan mengurangi risiko stack overflow.
Contoh Tail Recursion
def faktorial_tail(n, accumulator=1):
if n == 0:
return accumulator
else:
return faktorial_tail(n - 1, n * accumulator)
# Contoh penggunaan
print(faktorial_tail(5)) # Output: 120
Dalam contoh ini, faktorial_tail menggunakan parameter tambahan accumulator untuk menyimpan hasil perkalian sementara, dan panggilan rekursif adalah operasi terakhir dalam fungsi.
Kesimpulan Bab 6
Pada bab ini, kita telah membahas konsep dasar rekursi, beberapa algoritma rekursif klasik, dan pendekatan pembagian dan penaklukan. Rekursi adalah teknik yang sangat kuat dalam pemrograman, tetapi harus digunakan dengan hati-hati untuk menghindari masalah seperti stack overflow. Memahami rekursi dan cara mengimplementasikannya dengan benar adalah langkah penting dalam pengembangan algoritma yang efisien.
Di bab selanjutnya, kita akan mengeksplorasi lebih lanjut tentang algoritma dan struktur data yang lebih kompleks serta aplikasi praktis dalam pemrograman.