Rekursi di Clojure

Clojure tidak menyediakan perulangan imperatif berbasis variabel penanda yang diubah setiap iterasi, sehingga proses berulang dinyatakan dengan rekursi, yaitu pemanggilan fungsi terhadap dirinya sendiri dengan input yang menuju kasus dasar. Topik ini membahas mengapa rekursi naif dapat menghabiskan stack, bagaimana recur mencegah pertumbuhan stack, bagaimana loop menyatakan rekursi secara eksplisit, dan bagaimana pola akumulator menyusun hasil parsial. Contohnya mencakup faktorial dan pemrosesan antrean loket, termasuk eksekusi dengan satu juta langkah sebagai bukti keamanan stack.

Rekursi naif dan batas stack#

Rekursi naif memanggil dirinya sendiri sebelum perhitungan selesai, sehingga setiap pemanggilan menunggu hasil pemanggilan berikutnya. Rumus faktorial menyatakan pola ini dengan jelas.

Bentuk rekursifnya adalah $n! = n \times (n-1)!$ dengan kasus dasar $0! = 1$. Implementasi naif memindahkan kedua rumus tersebut ke dalam kode secara langsung.

(defn faktorial-naif
  [n]
  (if (zero? n)
    1
    (* n (faktorial-naif (dec n)))))

(println "(faktorial-naif 10) =" (faktorial-naif 10))

(faktorial-naif 10) = 3628800

Ekspresi (* n (faktorial-naif (dec n))) menahan perkalian hingga pemanggilan berikutnya kembali, sehingga setiap tingkat pemanggilan menyimpan satu frame pada stack yang berisi nilai n yang masih menunggu. Stack JVM berukuran terbatas dan umumnya hanya menampung ribuan hingga puluhan ribu frame untuk fungsi sederhana. Dengan input yang besar, frame bertumpuk melampaui batas itu dan program berhenti dengan StackOverflowError.

; tidak-dijalankan
; rekursi naif menumbuhkan stack satu frame per tingkat pemanggilan
; dan berhenti dengan StackOverflowError jauh sebelum satu juta langkah
(defn faktorial-naif
  [n]
  (if (zero? n)
    1
    (* n (faktorial-naif (dec n)))))

(println "(faktorial-naif 1000000) =" (faktorial-naif 1000000))

Blok di atas sengaja tidak dieksekusi karena kegagalannya sudah pasti terjadi. Kegagalan itu bukan pada logika perhitungannya, melainkan pada penyimpanan frame yang menunggu, dan masalah semacam ini diselesaikan dengan tail call.

recur dan posisi tail call#

Sebuah pemanggilan disebut tail call apabila tidak ada perhitungan yang menunggu hasilnya, sehingga pemanggilan itu menjadi langkah terakhir sebelum fungsi kembali. Pada faktorial-naif, perkalian (* n ...) masih menunggu, sehingga pemanggilan rekursifnya bukan tail call. JVM tidak menghilangkan tail call secara otomatis, sehingga Clojure menyediakan recur sebagai pemanggilan ulang yang menggunakan kembali frame yang sama. Stack tidak bertambah, dan prosesnya secara efektif menjadi perulangan.

Pola akumulator mengubah perhitungan yang menunggu menjadi tail call dengan membawa hasil parsial pada parameter tambahan. Fungsi jumlah-hingga berikut menjumlahkan bilangan dari n turun ke satu, dengan akumulator menyimpan jumlah parsial antar langkah.

(defn jumlah-hingga
  [n akumulator]
  (if (zero? n)
    akumulator
    (recur (dec n) (+ akumulator n))))

(println "(jumlah-hingga 1000000 0) =" (jumlah-hingga 1000000 0))

(jumlah-hingga 1000000 0) = 500000500000

Setiap langkah memanggil recur sebagai langkah terakhirnya, sehingga satu juta iterasi berjalan tanpa menumbuhkan stack sama sekali. recur di dalam defn mengikat ulang parameter fungsi, yaitu n menjadi satu lebih kecil dan akumulator menjadi jumlah barunya, sebagaimana penanda yang berpindah pada perulangan imperatif.

loop sebagai rekursi eksplisit#

loop mengikat nama-nama ke nilai awal sebagaimana let, sekaligus menandai titik kembali bagi recur. Bentuk ini menyatakan rekursi tanpa mendefinisikan fungsi terpisah dan lazim dipilih ketika proses berulangnya hanya digunakan satu kali. Faktorial dengan loop membawa dua binding, yaitu sisa sebagai penanda langkah dan akumulator sebagai hasil parsial.

(defn faktorial
  [n]
  (loop [sisa n
         akumulator 1]
    (if (zero? sisa)
      akumulator
      (recur (dec sisa) (* akumulator sisa)))))

(println "(faktorial 20) =" (faktorial 20))

(faktorial 20) = 2432902008176640000

Kasus dasarnya adalah sisa mencapai nol, dan setiap langkah mengikat ulang sisa menjadi satu lebih kecil sementara akumulator diperbesar dengan nilai sisa sebelumnya. Urutan perkalian bergerak dari satu hingga n, berlawanan dengan versi naif yang mengalikan dari n turun, tetapi hasilnya sama karena perkalian bersifat komutatif. Secara mekanisme, recur di dalam loop mengikat ulang binding loop, sedangkan di dalam defn mengikat ulang parameter, sehingga keduanya hanya berbeda pada tempat nilai awalnya dinyatakan.

Pola akumulator pada antrean loket#

Pola yang sama berlaku ketika yang diproses bukan angka, melainkan koleksi. Antrean loket berikut dilayani satu per satu, dan setiap langkah menghasilkan nilai baru tanpa mengubah data mana pun. Tiga binding dibawa antar langkah, yaitu sisa sebagai ekor antrean, nomor sebagai urutan layanan, dan terlayani sebagai daftar hasil.

(def antrean ["Ali" "Budi" "Citra" "Dewi"])

(loop [sisa antrean
       nomor 1
       terlayani []]
  (if (empty? sisa)
    (println "Dilayani:" terlayani)
    (do
      (println "Nomor" nomor "-" (first sisa))
      (recur (rest sisa) (inc nomor) (conj terlayani nomor)))))

Nomor 1 - Ali
Nomor 2 - Budi
Nomor 3 - Citra
Nomor 4 - Dewi
Dilayani: [1 2 3 4]

Kasus dasarnya adalah empty? pada sisa, dan setiap langkah memanggil rest untuk mengambil ekor antrean. Form do menyatukan dua hal dalam satu cabang, yaitu mencetak layanan dan melanjutkan perulangan. Data asli antrean tidak berubah sama sekali karena rest dan conj menghasilkan nilai baru, sehingga proses ini tetap murni meskipun bentuknya menyerupai perulangan imperatif. Bagian yang mencetak juga terpisah dari bagian yang menghitung, sehingga inti perulangannya dapat diuji tanpa efek samping.

Kesalahan umum#

Kesalahan pertama berupa recur yang tidak berada di posisi ekor. Ekspresi (inc (recur (dec n))) ditolak saat kompilasi karena hasil recur dibungkus inc, dan perbaikannya adalah membawa nilai melalui parameter akumulator hingga recur menjadi langkah terakhir. Kesalahan kedua berupa kasus dasar yang tidak tercapai. Setiap langkah wajib menggerakkan input menuju kasus dasar, misalnya (dec n) pada penjumlahan atau rest pada antrean, sehingga kondisi zero? atau empty? benar-benar terpenuhi.

Kesalahan ketiga berupa recur yang melintasi batas try. Pemanggilan recur tidak boleh melewati blok try, dan proses yang membutuhkan penanganan error di tengah perulangan sebaiknya membungkus satu langkah ke dalam fungsi terpisah. Kesalahan terakhir berupa pemilihan recur untuk pekerjaan yang lebih tepat dinyatakan dengan reduce. Apabila setiap langkah hanya menjumlahkan atau menggabungkan elemen, reduce menyatakan maksud tersebut lebih langsung, sedangkan loop dan recur dipertahankan untuk pola yang lebih bebas, misalnya membawa lebih dari satu akumulator.

Ringkasan#

• Rekursi naif menunda perhitungan hingga pemanggilan berikutnya kembali, sehingga frame bertumpuk pada stack dan berakhir dengan StackOverflowError pada kedalaman besar.
• recur memanggil ulang fungsi atau loop dengan menggunakan kembali frame yang sama, dan hanya legal pada posisi tail call.
• loop mengikat nama-nama ke nilai awal sebagaimana let dan menandai titik kembali bagi recur.
• Pola akumulator membawa hasil parsial melalui parameter, sehingga perhitungan yang menunggu berubah menjadi tail call yang aman terhadap stack.

Referensi#

• recur — ClojureDocs — Dokumentasi recur beserta catatan posisi tail call dan contoh penggunaannya.
• loop — ClojureDocs — Dokumentasi loop dengan contoh perulangan berbasis binding yang diikat ulang oleh recur.
• Functional Programming — Clojure.org — Referensi resmi pemrograman fungsional Clojure, termasuk bagian rekursi.