Algoritma rekursif menyelesaikan masalah dengan memanggil dirinya sendiri pada versi masalah yang lebih kecil. Ada tiga hal yang perlu ditentukan saat menulisnya: base case yang jelas, langkah pengecilan masalah, dan pemanggilan yang menuju base case. Panduan langkah demi langkah menulis algoritma rekursif ini memecah proses tersebut menjadi urutan yang bisa dikerjakan satu per satu.
Kegagalan menulis rekursi sering terjadi karena pemanggilan sudah ditulis sebelum tahu kapan fungsinya harus berhenti. Urutan langkah di bawah ini sengaja menaruh penentuan base case di depan supaya kesalahan itu tidak terjadi.
Kenali dulu bentuk masalah yang cocok diselesaikan rekursif
Rekursi masuk akal ketika sebuah masalah bisa dipecah menjadi salinan masalah yang sama dengan ukuran lebih kecil. Menghitung faktorial, membalik string, menelusuri pohon, dan menghitung deret Fibonacci memenuhi syarat ini. Versi kecil dari masalah itu menghasilkan nilai yang dipakai untuk membentuk hasil versi besar.
Masalah yang setiap langkahnya berbeda bentuk tidak cocok dibuat rekursif. Menghitung total belanja dari daftar harga lebih rapi dengan perulangan biasa. Sebelum menulis kode, jawab satu pertanyaan: apakah hasil untuk ukuran n bisa dibentuk dari hasil untuk ukuran n-1? Kalau jawabannya tidak, cari pendekatan lain.
Langkah 1: Tentukan base case lebih dulu
Base case adalah kondisi terkecil yang jawabannya sudah diketahui tanpa perlu memanggil fungsi lagi. Untuk faktorial, base case-nya n sama dengan 0 atau 1 yang hasilnya 1. Untuk pencarian elemen pada array, base case-nya bisa berupa indeks yang melewati batas array atau elemen yang sudah ditemukan.
Base case harus memenuhi dua syarat. Kondisinya bisa dicapai dari input awal yang wajar, dan jawabannya tidak bergantung pada pemanggilan fungsi. Fungsi rekursif yang base case-nya tidak pernah tercapai akan berhenti karena call stack penuh, dan pesan error yang muncul sering membingungkan pemula. Mengetahui cara membaca stack trace membantu di titik ini.
Periksa apakah base case mencakup semua kasus tepi
Input kosong, nilai negatif, dan panjang array nol sering lolos dari pemeriksaan. Daftarkan kemungkinan input terkecil yang sah, lalu pastikan setiap kemungkinan itu punya jawaban langsung. Untuk faktorial, n negatif tidak bermakna sehingga sebaiknya ditolak dengan pesan error yang jelas sejak awal.
Langkah 2: Rumuskan langkah pengecilan masalah
Bagian ini menentukan bagaimana ukuran masalah menyusut tiap pemanggilan. Faktorial menyusut satu angka per langkah, pencarian biner memotong setengah ruang pencarian, dan penelusuran pohon bergerak ke anak kiri lalu anak kanan. Tulis dulu aturan pengecilannya dalam kalimat biasa sebelum menyentuh kode.
Pastikan arah pengecilan selalu menuju base case. Kesalahan umum adalah menulis n + 1 padahal base case ada di angka 0. Periksa juga bahwa setiap cabang pemanggilan benar-benar mengurangi ukuran, termasuk cabang yang jarang terpakai.
Langkah 3: Tulis relasi rekurens dalam bentuk kode
Setelah base case dan aturan pengecilan jelas, tulis fungsinya. Contoh berikut menghitung faktorial secara rekursif dalam Python.
def faktorial(n):
if n < 0:
raise ValueError("n tidak boleh negatif")
if n <= 1:
return 1
return n * faktorial(n - 1)Perhatikan struktur fungsinya: pemeriksaan input, base case, lalu pemanggilan rekursif. Pola ini berlaku untuk hampir semua fungsi rekursif sederhana. Untuk kasus yang melibatkan dua cabang, seperti penelusuran pohon, hasil kedua cabang digabung setelah masing-masing selesai diproses.
Contoh dua cabang: menghitung kedalaman pohon biner
def kedalaman(node):
if node is None:
return 0
kiri = kedalaman(node.kiri)
kanan = kedalaman(node.kanan)
return 1 + max(kiri, kanan)Base case di sini adalah node kosong. Setiap pemanggilan bergerak satu tingkat lebih dalam, dan hasil kedua anak dibandingkan sebelum dikembalikan. Struktur data pohon dibahas lebih rinci di perbandingan struktur data untuk belajar algoritma.
Langkah 4: Telusuri eksekusi dengan contoh kecil
Jalankan fungsi secara manual untuk input kecil, misalnya faktorial(3). Tulis setiap pemanggilan beserta nilai yang dikembalikan. Cara ini memperlihatkan urutan pemanggilan dan kapan hasil mulai dijumlahkan kembali dari bawah ke atas.
- faktorial(3) memanggil faktorial(2)
- faktorial(2) memanggil faktorial(1)
- faktorial(1) mengembalikan 1 karena base case
- faktorial(2) mengembalikan 2 * 1 = 2
- faktorial(3) mengembalikan 3 * 2 = 6
Kalau hasil penelusuran manual berbeda dari dugaan, kesalahannya hampir selalu ada di base case atau di arah pengecilan. Perbaiki di sana sebelum menambah kasus uji lain.
Langkah 5: Hitung biaya dan risiko tumpukan
Fungsi rekursif sederhana seperti faktorial berjalan dalam waktu linear terhadap n. Setiap pemanggilan menambah satu lapisan pada call stack, sehingga input yang sangat besar bisa memicu stack overflow. Python secara bawaan membatasi kedalaman rekursi, dan batas itu jauh lebih kecil dari yang dibayangkan banyak orang.
Kalau kedalaman rekursi diprediksi besar, pertimbangkan versi iteratif atau tambahkan memoization untuk masalah yang punya submasalah berulang. Deret Fibonacci naif adalah contoh klasik yang boros karena menghitung nilai yang sama berkali-kali.
| Masalah | Base case | Pengecilan |
|---|---|---|
| Faktorial | n <= 1 | n – 1 |
| Fibonacci | n <= 1 | n – 1 dan n – 2 |
| Pencarian biner | kiri > kanan | setengah ruang |
| Penelusuran pohon | node kosong | anak kiri dan kanan |
Langkah 6: Uji dengan kasus tepi dan bandingkan hasil
Uji fungsi pada base case langsung, satu langkah di atas base case, dan input acak berukuran sedang. Bandingkan hasilnya dengan versi iteratif yang sudah pasti benar. Untuk fungsi yang mengembalikan daftar, periksa juga urutan elemennya.
Saat pengujian gagal, pesan error yang muncul sebaiknya menunjukkan input yang bermasalah dan aturan yang dilanggar. Prinsip yang sama berlaku saat menulis pesan error untuk pengguna aplikasi: sebutkan apa yang salah dan langkah perbaikannya, seperti dijelaskan pada cara menulis pesan error yang membantu pengguna.
Langkah 7: Sederhanakan dan dokumentasikan
Setelah fungsi berjalan benar, rapikan penamaannya dan tambahkan komentar singkat pada base case serta relasi rekurens. Komentar tidak perlu menjelaskan sintaks, cukup alasan mengapa base case dipilih demikian. Fungsi rekursif yang baik bisa dibaca ulang berbulan-bulan kemudian tanpa menebak-nebak.
Latihan rutin mempercepat proses ini. Mulai dari masalah kecil seperti membalik string, lalu naik ke penelusuran graf. Beberapa pola rekursif pada graf dan pencarian jalur muncul dalam algoritma pencarian yang sering muncul di soal coding interview, dan contoh penerapannya bisa dilihat pada panduan menerapkan algoritma Dijkstra.
Ringkasan
Menulis algoritma rekursif berarti menentukan kapan berhenti, bagaimana mengecilkan masalah, lalu menyusun pemanggilan yang selalu bergerak menuju titik berhenti itu. Telusuri eksekusi dengan input kecil sebelum menambah kasus uji yang lebih rumit, dan hitung kedalaman rekursi kalau inputnya berpotensi besar.
Pertanyaan yang Sering Diajukan
Apakah semua fungsi rekursif bisa diubah menjadi iteratif?
Bisa. Setiap rekursi dapat diganti dengan perulangan dan tumpukan buatan sendiri. Untuk masalah sederhana, versi iteratif biasanya lebih hemat memori. Untuk penelusuran pohon atau graf, versi rekursif sering lebih mudah dibaca meski memakai call stack.
Kapan sebaiknya memakai memoization?
Pakai memoization ketika fungsi rekursif memanggil dirinya dengan argumen yang sama berkali-kali, seperti pada Fibonacci atau perhitungan jarak pada graf. Simpan hasil setiap argumen di dictionary atau array, lalu periksa isinya sebelum menghitung ulang.
Bagaimana cara memperbaiki error recursion depth exceeded?
Cari dulu penyebabnya. Kalau base case tidak pernah tercapai, perbaiki kondisi pengecilan masalah. Kalau kedalamannya memang wajar tetapi besar, ubah ke versi iteratif atau naikkan batas kedalaman rekursi sesuai kebutuhan, sambil memastikan memori tetap memadai.