KAL
Menu

Rekursi sebagai iterasi

Rekursi sebagai mekanisme pengulangan pada bahasa tanpa pernyataan loop.

Daftar isi

Topik ini menjelaskan mengapa dan bagaimana rekursi menjadi satu-satunya mekanisme pengulangan di Erlang, beserta bentuk dasarnya pada list: kasus dasar, kasus rekursif, dan pemilihan klausul lewat pencocokan pola. Setelah membaca, fungsi pengolah list sederhana dapat ditulis dan dibaca tanpa pernyataan perulangan.

Bahasa tanpa pernyataan perulangan#

Erlang tidak memiliki pernyataan seperti while atau for. Keputusan desain ini berakar dari sifat bahasanya: variabel diikat sekali, sehingga penghitung yang diperbarui setiap iterasi tidak mungkin ada. Pengulangan dinyatakan dengan fungsi rekursif, yaitu fungsi yang memanggil dirinya sendiri dengan data yang menyempit sampai kasus dasarnya tercapai. Data yang menyempit itulah yang mengambil peran penghitung: setiap pemanggilan menerima kondisi yang lebih dekat ke selesai, sehingga variabel penghitung yang berubah-ubah tidak dibutuhkan sama sekali.

Bentuk yang paling sering dijumpai adalah rekursi atas list. List diuraikan dengan pola [K | S]: klausa pertama menangani list kosong sebagai kasus dasar, dan klausa kedua memproses kepala lalu memanggil dirinya dengan ekor. Modul berikut menjumlahkan dan menghitung panjang list dengan bentuk tersebut:

erlang jumlah.erl 
-module(jumlah).
-export([total/1, panjang/1]).

total([]) -> 0;
total([K | S]) -> K + total(S).

panjang([]) -> 0;
panjang([_ | S]) -> 1 + panjang(S).

Setiap fungsi memiliki dua klausa yang dipilih lewat pencocokan pola. Klausa total([]) mengembalikan 0 tanpa memanggil apa pun, sedangkan klausa total([K | S]) menghitung K + total(S), sehingga pekerjaan berlanjut ke list yang lebih pendek. Fungsi panjang/1 memakai variabel tanpa nama _ karena isinya tidak diperlukan, cukup jumlahnya.

Menjalankan rekursi#

Kompilasi dan panggil kedua fungsi dari shell:

erlang Mencoba modul rekursif 
Erlang/OTP 29 [erts-17.1.1] [source] [64-bit] [smp:2:2] [ds:2:2:10] [async-threads:1] [jit:ns]

Eshell V17.1.1 (press Ctrl+G to abort, type help(). for help)
1> c(jumlah).
{ok,jumlah}
2> jumlah:total([2, 5, 1]).
8
3> jumlah:total([]).
0
4> jumlah:panjang([2, 5, 1]).
3
5> jumlah:panjang([]).
0

Pemanggilan total([2, 5, 1]) bergerak seperti berikut: 2 + total([5, 1]), lalu 2 + (5 + total([1])), lalu 2 + (5 + (1 + total([]))), dan list kosong mengembalikan 0 sehingga penjumlahan naik kembali menjadi 8. Kasus dasar bukan formalitas, melainkan jangkar yang menghentikan pergerakan. Menghapusnya membuat setiap pemanggilan berakhir dengan error function clause karena tidak ada klausa yang menerima list kosong.

Membaca arah pengolahan#

Pada bentuk di atas, operasi utama dilakukan setelah pemanggilan rekursif kembali, sebagaimana tampak pada K + total(S): penjumlahan menunggu hasil ekor selesai dulu. Bentuk ini disebut rekursi tubuh (body recursion), dan arah kerjanya bisa dibaca dari posisi operator. Bila operasi dilakukan sebelum memanggil kembali, pemrosesan bergerak dari kepala ke ekor tanpa menunggu, sebagaimana akan dibangun pada topik akumulator dan tail call.

Perbedaan arah ini bukan sekadar gaya. Rekursi tubuh membangun ekspresi yang menunggu di tumpukan pemanggilan, sedangkan bentuk yang memanggil sebagai langkah terakhir bisa diganti oleh VM dengan lompatan biasa. Untuk list pendek keduanya identik dari luar, tetapi kebiasaan membaca arah pengolahan sejak awal membuat topik akumulator dan tail call lebih mudah diikuti.

Rekursi bercabang#

Fungsi rekursif tidak wajib memanggil dirinya sekali. Deret Fibonacci memanggil dirinya dua kali per langkah, dan kedua cabang bergerak menuju kasus dasarnya masing-masing:

erlang fib.erl 
-module(fib).
-export([hitung/1]).

hitung(0) -> 0;
hitung(1) -> 1;
hitung(N) -> hitung(N - 1) + hitung(N - 2).

Ketiga klausanya bekerja berurutan: kasus dasar 0 dan 1 menghentikan cabang, sedangkan klausa ketiganya menjumlahkan dua rekursi dengan masukan yang menyempit. Hasil eksekusinya:

erlang Deret Fibonacci dengan rekursi bercabang 
4> c(fib).
{ok,fib}
5> fib:hitung(10).
55

Hasil 55 untuk suku kesepuluh sudah benar, tetapi bentuk ini menyembunyikan pekerjaan berulang: menghitung suku ke-10 memanggil hitung(8) dua kali secara terpisah, dan penggandaan cabang itu bertumbuh eksponensial terhadap masukan. Contoh ini tetap patut dipahami karena memperlihatkan bentuk rekursi yang sah, sementara perbaikannya, yaitu membawa dua suku terakhir sebagai pasangan akumulator, memakai pola yang sama dengan topik akumulator dan tail call.

Rekursi tanpa list#

Pola yang sama bekerja pada bilangan, bukan hanya list. Penghitung mundur menyempit dari N menuju 0, dan dalam shell bentuknya memanfaatkan fungsi bernama, yaitu fun Nama(Arg) -> ... end yang bisa memanggil dirinya:

erlang Penghitung mundur dengan fun bernama 
1> Hitung = fun Mundur(N) when N > 0 -> io:format("~p... ", [N]), Mundur(N - 1); Mundur(0) -> selesai end.
#Fun<erl_eval.19.130099583>
2> Hitung(3).
3... 2... 1... selesai

Nama Mundur hanya terlihat di dalam fungsi itu sendiri, sekaligus menjawab kebutuhan rekursi pada nilai fun. Guard N > 0 menandai klausa yang masih bekerja dan Mundur(0) sebagai kasus dasar, persis seperti pasangan list dan list kosong. Bentuk ini memperlihatkan bahwa rekursi adalah alat umum untuk pekerjaan berulang, dan list hanyalah kasus penggunaannya yang paling sering.

Ringkasan#

  • Erlang tidak memiliki pernyataan while atau for karena variabel tidak dapat diperbarui, sehingga pengulangan dinyatakan dengan fungsi rekursif.
  • Bentuk dasarnya adalah dua klausa: list kosong sebagai kasus dasar dan [K | S] sebagai kasus rekursif dengan data yang menyempit.
  • Variabel tanpa nama _ dipakai bila isi elemen tidak diperlukan, sebagaimana pada panjang/1.
  • Rekursi tubuh menempatkan operasi setelah pemanggilan rekursif sehingga pekerjaan menunggu di tumpukan, dan bentuk ini menjadi pembanding bagi tail call.
  • Rekursi bercabang memanggil dirinya lebih dari sekali per langkah dan tetap sah, tetapi cabang yang berulang bisa membuat pekerjaan bertumbuh eksponensial.
  • Fungsi bernama fun Nama(…) -> … end memungkinkan rekursi di dalam nilai fun, dengan nama yang hanya terlihat di dalam fungsinya.

Kesalahan umum#

  • Menghapus atau salah menuliskan kasus dasar. Tanpa klausa list kosong, setiap pemanggilan berakhir dengan error function_clause karena list menyempit terus sampai tidak ada pola yang cocok. Kasus dasar adalah jangkar, bukan formalitas.
  • Memanggil fungsi dengan aritas yang keliru. Definisi total/1 hanya memiliki satu argumen, dan pemanggilan total(L, Acc) mencari fungsi lain yang tidak diekspor. Perhatikan aritas pada pesan error undefined function.
  • Menghitung sesuatu yang sudah disediakan modul lists. Sebelum menulis rekursi sendiri, periksa dulu modul lists. Fungsi umum seperti penjumlahan, penyaringan, dan pembalikan sudah tersedia dan teruji.

Referensi#