Rekursi

Rekursi adalah teknik memecahkan masalah dengan memanggil fungsi itu sendiri pada masukan yang lebih kecil, hingga mencapai kasus yang dijawab tanpa pemanggilan lagi. Topik ini membahas dua komponen wajibnya melalui faktorial dan Fibonacci, menerapkannya pada pencarian biner sebagai contoh divide-and-conquer, serta menutup dengan batas rekursi dan cara menghindari perhitungan ulang.

Kasus dasar dan langkah rekursi#

Setiap fungsi rekursif memuat dua bagian yang wajib ada. Kasus dasar (base case) menghentikan pemanggilan dengan mengembalikan nilai secara langsung, sedangkan langkah rekursi memecahkan satu unit masalah lalu memanggil dirinya dengan masukan yang mendekati kasus dasar. Tanpa salah satunya, pemanggilan tidak pernah berhenti.

Faktorial memuat kedua bagian itu secara alami. Definisinya dituliskan sebagai berikut, dengan kasus dasar $0! = 1$.

def faktorial(n):
    if n <= 1:
        return 1
    return n * faktorial(n - 1)

for n in [0, 1, 5]:
    print(n, faktorial(n))

0 1
1 1
5 120

Pemanggilan faktorial(5) membentuk rantai faktorial(4) sampai faktorial(1), lalu nilai dikembalikan berlapis-lapis dengan perkalian di setiap tingkat. Syarat n <= 1 sekaligus menghentikan rantai pada 1, sehingga kasus n = 0 ikut tertangani tanpa cabang tambahan.

Setiap pemanggilan membentuk satu bingkai (frame) tersendiri di memori, lengkap dengan nilai parameternya, dan bingkai itu ditutup setelah nilai kembaliannya diterima. Rantai faktorial(5) sampai faktorial(1) berarti lima bingkai menunggu bersamaan, dan jumlah bingkai itulah yang dibatasi interpreter. Untuk masukan yang sangat besar, versi perulangan menghindari penumpukan bingkai tersebut.

Fibonacci dan harga pemanggilan berulang#

Barisan Fibonacci menetapkan dua kasus dasar sekaligus, yaitu angka ke-0 bernilai 0 dan angka ke-1 bernilai 1, sedangkan angka berikutnya adalah jumlah dua angka sebelumnya. Definisi ganda ini langsung menjadi rekursi yang memanggil fungsinya dua kali.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for n in [6, 10, 20]:
    print(n, fibonacci(n))

6 8
10 55
20 6765

Hasilnya sesuai definisi, tetapi bentuk rekursi ganda ini mengulang pekerjaan yang sama berkali-kali. Penghitung pemanggilan berikut memperlihatkan berapa kali fungsi benar-benar dijalankan untuk menghasilkan satu nilai.

pemanggilan = 0

def fibonacci_hitung(n):
    global pemanggilan
    pemanggilan += 1
    if n <= 1:
        return n
    return fibonacci_hitung(n - 1) + fibonacci_hitung(n - 2)

for n in [10, 20]:
    pemanggilan = 0
    fibonacci_hitung(n)
    print("n =", n, "dipanggil", pemanggilan, "kali")

n = 10 dipanggil 177 kali
n = 20 dipanggil 21891 kali

Untuk n = 20, fungsi dipanggil 21891 kali hanya untuk memproduksi satu nilai, karena cabang kiri dan kanan menghitung angka yang sama berulang-ulang. Pertumbuhannya mendekati eksponensial, ditulis $O(2^n)$, sehingga nilai n yang sedikit lebih besar sudah terasa lambat.

Divide-and-conquer pada pencarian biner#

Pola divide-and-conquer membagi masalah menjadi bagian yang lebih kecil, menyelesaikan salah satunya, dan mengabaikan sisanya. Pencarian biner pada data terurut memakai pola ini, yaitu membandingkan target dengan elemen tengah, lalu meneruskan pencarian pada separuh yang relevan saja.

def cari_biner(data, target, kiri, kanan):
    if kiri > kanan:
        return -1
    tengah = (kiri + kanan) // 2
    if data[tengah] == target:
        return tengah
    if data[tengah] < target:
        return cari_biner(data, target, tengah + 1, kanan)
    return cari_biner(data, target, kiri, tengah - 1)

angka = [2, 5, 8, 12, 16, 23, 38]
print(cari_biner(angka, 16, 0, len(angka) - 1))
print(cari_biner(angka, 9, 0, len(angka) - 1))

4
-1

Angka 16 ditemukan pada indeks 4 setelah beberapa kali pembagian, sedangkan 9 berakhir pada rentang kosong sehingga dikembalikan -1. Kasus dasarnya adalah rentang kosong. Setiap langkah memotong rentang menjadi separuh, sehingga kedalaman rekursi tumbuh secara logaritmik, ditulis $O(\log n)$, bukan eksponensial. Parameter kiri dan kanan membawa batas pencarian yang terus menyempit, sehingga tidak ada data yang disalin pada setiap pemanggilan.

Batas rekursi dan mencegah perhitungan ulang#

Python menetapkan batas kedalaman rekursi agar rantai tanpa akhir tidak menghabiskan memori. Fungsi yang melewati batas tersebut dihentikan dengan error RecursionError.

def hitung_mundur(n):
    return hitung_mundur(n + 1)

try:
    hitung_mundur(1)
except RecursionError:
    print("RecursionError: batas rekursi terlampaui")

RecursionError: batas rekursi terlampaui

Fungsi hitung_mundur memanggil dirinya dengan n yang terus bertambah dan tidak pernah berhenti, sehingga interpreter menghentikannya pada batas kedalaman. Batas itu dapat diperiksa melalui sys.getrecursionlimit() dan diubah dengan sys.setrecursionlimit(), tetapi peningkatannya tidak menyembuhkan rekursi yang salah dan hanya menunda kegagalannya.

Perhitungan ulang pada Fibonacci dapat dihilangkan dengan menyimpan hasil yang sudah dihitung. Pustaka standar menyediakan decorator functools.cache yang mencatat setiap hasil pemanggilan, sehingga pemanggilan berikutnya dengan argumen yang sama dijawab langsung dari catatan.

from functools import cache

@cache
def fibonacci_cepat(n):
    if n <= 1:
        return n
    return fibonacci_cepat(n - 1) + fibonacci_cepat(n - 2)

print(fibonacci_cepat(30))

832040

Dengan cache, fibonacci_cepat(30) selesai dalam waktu singkat karena setiap angka hanya dihitung satu kali. Teknik menyimpan hasil seperti ini disebut memoization. Hasil akhirnya identik dengan definisi rekursi, tetapi biaya perhitungannya jauh lebih kecil.

Kesalahan umum#

Kesalahan pertama adalah langkah rekursi yang menjauhi kasus dasar. Kasus dasarnya ada, tetapi masukannya bergerak ke arah yang salah, sehingga batas rekursi tetap terlampaui.

def hitung_mundur_dari(n):
    if n == 0:
        return 0
    return hitung_mundur_dari(n + 1)

try:
    hitung_mundur_dari(5)
except RecursionError:
    print("RecursionError: kasus dasar tidak pernah tercapai")

RecursionError: kasus dasar tidak pernah tercapai

Perbaikannya memastikan setiap langkah bergerak menuju kasus dasar, misalnya memanggil dirinya dengan n - 1 apabila kasus dasarnya 0. Arah langkah dan letak kasus dasar wajib saling cocok.

Kesalahan kedua adalah melupakan return pada langkah rekursi. Pemanggilan dalam tetap berjalan, tetapi hasilnya terbuang, sehingga fungsi tingkat teratas mengembalikan None.

def faktorial_tanpa_return(n):
    if n <= 1:
        return 1
    faktorial_tanpa_return(n - 1)

print(faktorial_tanpa_return(5))

None

Baris terakhir seharusnya return n * faktorial_tanpa_return(n - 1), sehingga setiap tingkat meneruskan hasil tingkat di bawahnya. Aturannya sederhana, yaitu nilai yang dihitung cabang rekursi harus dikembalikan, bukan hanya dipanggil.

Kesalahan ketiga adalah memakai rekursi ganda yang murni pada masukan besar tanpa menyimpan hasilnya. Fibonacci murni memanggil dirinya berkali-kali untuk masukan yang sama sebagaimana ditunjukkan penghitung pemanggilan, sehingga masukan yang sedikit lebih besar sudah memakan waktu berlebih. Solusinya adalah menambah cache atau menyusun ulang perhitungan secara berurutan. Pilihannya dinilai dari ukuran masukan yang diharapkan.

Ringkasan#

• Fungsi rekursif memuat kasus dasar yang menghentikan pemanggilan dan langkah rekursi yang mendekati kasus dasar tersebut.
• Rekursi ganda seperti Fibonacci memanggil fungsi berkali-kali untuk masukan yang sama, dengan biaya yang tumbuh mendekati eksponensial.
• Pencarian biner menerapkan pola divide-and-conquer dengan kedalaman yang tumbuh secara logaritmik.
• Rekursi yang kasus dasarnya tidak tercapai berhenti dengan RecursionError, dan functools.cache mencegah perhitungan ulang dengan menyimpan hasil pemanggilan.

Referensi#

• functools — Higher-order functions and operations on callable objects — Python Software Foundation — Dokumentasi resmi decorator functools.cache.
• RecursionError — Python Software Foundation — Dokumentasi exception yang muncul ketika batas rekursi terlampaui.
• sys.setrecursionlimit — Python Software Foundation — Dokumentasi batas kedalaman rekursi dan cara mengubahnya.