Rekursi menjadi iterasi

Fungsi rekursif memiliki batas kedalaman, dan batas itu dapat dilampaui pada masukan yang besar. Topik ini membahas kapan konversi rekursi menjadi iterasi perlu dilakukan, bagaimana stack eksplisit menggantikan peran call stack, dan kapan konversi justru tidak perlu. Contohnya penelusuran subhimpunan yang dikerjakan dua kali, rekursif dan iteratif, dengan keluaran yang identik, termasuk urutannya.

Batas kedalaman rekursi#

CPython membatasi kedalaman rekursi sekitar 1000 frame secara bawaan. Batas ini melindungi program dari kehabisan memori stack, tetapi menjadi tembok ketika masukan bertumbuh, misalnya penelusuran daftar yang kedalamannya tumbuh linear dengan panjang daftar. Bahasa lain menampilkan masalah serupa dalam bentuk yang berbeda: Java melempar StackOverflowError pada kedalaman yang terlalu besar, dan C tanpa pengaturan ukuran stack yang besar berperilaku serupa. Penelusuran pada struktur bercabang memiliki kedalaman yang jauh lebih pendek daripada jumlah simpulnya, sehingga korban batas ini biasanya rekursi yang bergerak linear, seperti mengosongkan daftar satu per satu. Angka batas tersebut dapat diperiksa langsung:

import sys

print("batas rekursi default:", sys.getrecursionlimit())

batas rekursi default: 1000

Menaikkan batas dengan sys.setrecursionlimit() memang tersedia, tetapi langkah itu hanya menggeser masalah. Memori stack yang nyata tetap terbatas, dan proses dapat mati mendadak bila dipaksa menumpuk frame jauh melampaui kapasitasnya. Konversi ke iterasi menyelesaikan akar persoalannya, sebab perulangan tidak menumpuk frame sama sekali, sehingga kedalaman yang tadinya terbatas kini hanya bergantung pada memori utama yang jauh lebih longgar. Konsekuensinya, versi iteratif dapat dijalankan pada ukuran masukan yang membuat versi rekursif berhenti dengan error.

Stack eksplisit menyimpan pekerjaan#

Kunci konversinya adalah menyadari bahwa call stack hanyalah penyimpan pekerjaan yang belum selesai. Penyimpan itu dapat digantikan oleh struktur data biasa, biasanya list yang diperlakukan sebagai stack dengan append() untuk menumpuk dan pop() untuk mengambil teratas. Setiap kali versi rekursif memanggil diri, versi iteratif menumpuk satu pekerjaan pada list. Setiap kali versi rekursif kembali, versi iteratif memunculkan pekerjaan teratas dan mengerjakannya pada putaran berikutnya.

Isi pekerjaannya adalah seluruh informasi yang sebelumnya tersimpan dalam frame, misalnya indeks elemen yang sedang diputuskan dan jalur yang sudah dibangun. Karena tumpukan itu kini milik program sendiri, jumlahnya hanya dibatasi memori utama, bukan batas rekursi. Kompleksitas waktunya tidak berubah, tetapi ketahanan terhadap kedalaman yang besar meningkat. Gambar berikut membandingkan kedua penyimpan pekerjaan itu pada masukan yang sama:

Pada gambar, satu frame rekursif dan satu elemen stack eksplisit memuat informasi yang persis sama, yaitu indeks keputusan dan jalurnya. Perbedaannya ada pada pemiliknya: frame dikelola runtime secara otomatis, sedangkan stack eksplisit dikelola program dan tidak diawasi batas rekursi.

Konversi subhimpunan langkah demi langkah#

Subhimpunan dari tiga huruf dipilih sebagai contoh karena pohonnya pendek namun lengkap. Versi rekursif memutuskan pakai atau lewati untuk satu elemen lalu memanggil diri untuk elemen berikutnya, sedangkan versi iteratif menumpuk pasangan indeks dan jalur pada stack lalu mengulang sampai stack kosong. Kedua fungsi berikut menerima masukan yang sama:

# subhimpunan.py
# Dua versi penelusuran subhimpunan untuk masukan yang sama.

def subhimpunan_rekursif(item, i=0, jalur=()):
    # versi rekursif: keputusan pakai atau lewati untuk item[i]
    if i == len(item):
        return [jalur]
    dengan = subhimpunan_rekursif(item, i + 1, jalur + (item[i],))
    tanpa = subhimpunan_rekursif(item, i + 1, jalur)
    return dengan + tanpa

def subhimpunan_iteratif(item):
    # versi iteratif: stack eksplisit menyimpan pekerjaan (indeks, jalur)
    hasil, stack = [], [(0, ())]
    while stack:
        i, jalur = stack.pop()
        if i == len(item):
            hasil.append(jalur)
        else:
            # lewati item[i] ditumpuk dahulu agar cabang pakai dieksekusi lebih dulu
            stack.append((i + 1, jalur))
            stack.append((i + 1, jalur + (item[i],)))
    return hasil

data = ("a", "b", "c")
print("rekursif:", subhimpunan_rekursif(data))
print("iteratif:", subhimpunan_iteratif(data))
print("sama     :", subhimpunan_rekursif(data) == subhimpunan_iteratif(data))

rekursif: [('a', 'b', 'c'), ('a', 'b'), ('a', 'c'), ('a',), ('b', 'c'), ('b',), ('c',), ()]
iteratif: [('a', 'b', 'c'), ('a', 'b'), ('a', 'c'), ('a',), ('b', 'c'), ('b',), ('c',), ()]
sama     : True

Keluaran kedua versi sama persis, termasuk urutannya. Kuncinya ada pada urutan penumpukan: cabang lewati ditumpuk lebih dahulu, sehingga cabang pakai berada di atas dan dieksekusi lebih dulu, sama seperti urutan panggilan versi rekursif. Bila urutan ini terbalik, kedua fungsi masih menghasilkan himpunan jawaban yang sama, tetapi urutan pencetakannya berbeda. Jalur pada kedua versi disimpan sebagai tuple yang tidak dapat diubah, sehingga setiap cabang menerima keadaan yang aman sejak ditumpuk dan tidak ada perubahan silang antarcabang.

Kapan konversi tidak perlu#

Konversi bukan kewajiban bagi semua fungsi rekursif. Kedalaman $O(\log n)$, misalnya pencarian biner atau pembagian masukan menjadi dua bagian, aman dibiarkan rekursif. Ribuan frame sudah menampung masukan berukuran $2^{1000}$, karena kedalamannya hanya bertambah satu setiap kali masukan melipat ganda. Angka sebesar itu jauh melampaui memori apa pun, sehingga pertanyaan batas kedalaman tidak pernah muncul. Rekursi pada pohon yang seimbang juga bertahan dengan alasan sama, karena kedalamannya proporsional terhadap logaritma banyaknya simpul.

Konversi menjadi wajar pada tiga keadaan. Pertama, kedalaman yang tumbuh linear dengan masukan, seperti penelusuran daftar panjang satu per satu. Kedua, lingkungan dengan batas stack yang kecil, misalnya lingkungan tertanam (embedded) atau pemanggilan fungsi dari thread berukuran sempit. Ketiga, rekursi yang memanggil diri berkali-kali pada submasukan yang sama. Untuk keadaan ketiga, yang dibutuhkan sebenarnya adalah memoisasi atau pemrograman dinamis, karena stack eksplisit saja tidak menyembuhkan pekerjaan yang diulang, ia hanya menumpuknya kembali.

Keputusan terakhir selalu berbasis pengukuran, bukan selera. Jalankan versi rekursif pada masukan terbesar yang realistis, lihat apakah batas kedalaman benar-benar tersentuh, baru konversi bila perlu. Kode iteratif dengan stack eksplisit lebih panjang dan lebih mudah salah urutannya, sehingga harganya perlu dibayar hanya bila ada manfaat yang terukur.

Kesalahan umum#

Kesalahan paling sering adalah urutan penumpukan yang terbalik. Penumpukan ditulis mengikuti urutan membaca kode, padahal pop() mengambil elemen terakhir, sehingga cabang yang seharusnya dikerjakan lebih dulu justru tertimbun di bawah. Akibatnya keluaran berurutan salah meskipun jawabannya tetap lengkap, dan kekeliruan ini sulit terlihat bila urutan keluaran tidak diperiksa pada masukan kecil. Cara tercepat menangkapnya adalah mencetak keluaran kedua versi berdampingan pada masukan tiga elemen, seperti yang dilakukan berkas contoh.

Kesalahan kedua adalah pekerjaan yang kehilangan konteksnya. Menumpuk hanya indeks tanpa jalur, atau menumpuk jalur yang masih diubah-ubah oleh cabang lain, menghasilkan jawaban yang saling mencampur. Salin jalur ke tuple atau list baru setiap kali pekerjaan ditumpuk, seperti yang dilakukan berkas di atas lewat jalur + (item[i],). Kesalahan ketiga yang menyertainya adalah menumpuk dua kali atau memunculkan dua kali pada satu cabang, sehingga pekerjaan digandakan atau hilang dan hasilnya berantakan. Dengan dua kebiasaan ini, konversi dapat diverifikasi lewat keluaran, bukan lewat keyakinan bahwa kodenya sudah benar.

Ringkasan#

• Batas kedalaman rekursi Python sekitar 1000 frame, dan konversi ke iterasi menghapus batas itu sepenuhnya.
• Stack eksplisit, biasanya list dengan append() dan pop(), menyimpan pekerjaan yang sebelumnya disimpan frame rekursif.
• Urutan penumpukan harus dibalik dari urutan baca kode, karena pop() mengambil elemen terakhir.
• Kedalaman $O(\log n)$ tidak perlu dikonversi, sedangkan kedalaman linear pada masukan besar adalah kandidat konversi yang utama.

Referensi#

• sys — System-specific parameters and functions — Python documentation — Dokumentasi getrecursionlimit() dan setrecursionlimit() beserta perilaku batas kedalaman rekursi.
• Algorithms, 4th Edition — Princeton University — Bahan ajar algoritma yang membahas stack dan penelusuran graf secara rekursif maupun iteratif.