ITERASI VERSUS REKURSI: SEBUAH PERBANDINGAN

ITERASI VERSUS REKURSI: SEBUAH PERBANDINGAN Aditya Rama Mitra, SSi, MT." Abstract It is believed by many students who are taking programming and/or data structure class(es), that for any iterations there are their alternative recursive versions. These do not hold vice versa. In fact, in some situations that believe applies well; but still there is no guarantee that the alternative will always exist and is easily constructed. However, recursion is recommended for use wherever warranted. Despite the pros and cons of the ultimate use of recursion instead of iteration, this paper presents a brief summary on both versions that aims to underlie sound principles for students that they may follow through an intellectual process of determining a scheme which will fit their needs. The choice between iteration and recursion, therefore, should not be based merely on "taste" matter, but expectantly, elegant foundation.

1. PENDAHULUAN Dalam mata kuliah "Algoritma dan Pemrograman" yang berkiblat pada paradigma pemrograman imperatif (disebut juga disini sebagai paradigma pemrograman prosedural), iterasi dan rekursi disajikan sebagai dua pokok bahasan terpisah. Sekalipun demikian iterasi dan rekursi merupakan dua teknik penyelesaian yang berbeda dalam cara kerjanya bagi persoalan-persoalan repetisi (yang seringkali sama). Esensi dari sebuah persoalan repetisi sendiri adalah pengulangan aksi atau aksi yang dilakukan berulang kali dan disyaratkan untuk berhenti pada suatu saat. Bagi manusia, pengulangan aksi adalah sangat natural. Apakah dengan demikian rekursi pun natural? Bagi sebagian besar mahasiswa ternyata rekursi tidak dapat disejajarkan dalam cara berpikir yang sama. Bisa jadi, rekursi tidak tampak natural dalam praktik realisasi algoritma ketika solusi iteratif telah diperoleh. Dalam tulisannya [3] Zimmer menyebutkan dua penyebabnya, yaitu iterasi disajikan mendahului rekursi dan, yang lebih mendasar dari itu, penjelasan rekursi dilakukan dengan buruk. Sangat beralasan jika efek dari pemahaman yang kurang kuat disertai dengan konsep yang kurang tepat mengenai rekursi berlanjut hingga mata kuliah di tingkat lebih tinggi. Salah satu diantara mata kuliah yang memprasyaratkan pengambilan Algoritma dan Pemrograman adalah Struktur Data. Dalam mata kuliah ini peran rekursi tampak sangat menonjol, yang berarti sekaligus meminta porsi perhatian yang lebih besar dari mahasiswa relatif ketimbang iterasi. Untuk struktur-struktur seperti pohon (free) dan geraf (graph) rekursi tampaknya merupakan solusi terbaik bagi realisasi algoritma manipulasinya. Di ujung yang lain, implementasi dari realisasi tersebut membutuhkan bahasa pemrograman yang mendukung rekursi. Persoalannya bisa jadi sangat berbeda jika keputusan terbaik untuk realisasi algoritma dimaksud adalah rekursi, tetapi bahasa pemrograman yang hendak

' Dosen Tetap Fakultas llmu Komputer UPH Iterasi versus Rekursi: Sebuah Perbandingan (Aditya R. Mitra)

11

digunakan tidak mendukung hal tersebut. Sebaliknya, beberapa bahasa pemrograman tertentu (seperti Lisp, sebuah bahasa pemrograman fungsional) tidak mengenal konstruktor iterasi, sehingga akibatnya iterasi diekspresikan justru dalam terminologi rekursi. Dalam penyajian materi kuliah Algoritma dan Pemrograman, bahasan iterasi memang diberikan mendahului rekursi. Iterasi diekspresikan dalam terminologi konstruk repetisi (repetition construct) yang dikenal, seperti w h i l e - d o , r e p e a t u n t i l , atau i t e r a t e . Bahasan rekursi, di sisi lain, disajikan setelah bahasan fungsi dan prosedur. Kenyataan bahwa rekursi tidak dapat berdiri sendiri tanpa ada yang menginvokasinya menjelaskan dengan baik mengapa rekursi dibahas setelah fungsi dan prosedur. Dari pengamatan selama ini, rekursi dipandang kebanyakan mahasiswa sebagai sebuah alternatif untuk solusi iteratif bagi persoalan yang sama. Persoalan yang sering ditemui dalam kelas ataupun kegiatan praktikum adalah kesulitan mahasiswa di dalam mengkonstruksi rekursi untuk persoalan repetisi yang diberikan. Dalam tulisan yang sama [3] Zimmer bahkan menyebutkan adanya ketakutan di kalangan pemrogram yunior untuk bekerja dengan rekursi. Bisa jadi di kalangan peserta kuliah, kesulitan bekerja dengan rekursi bukan sebatas persoalan pemilihan teknik yang tepat, tetapi lebih merupakan manifestasi dari semacam ketakutan terhadap rekursi (fear of recursion). Terlepas dari kebenaran akan pendapat adanya ketakutan untuk bekerja dengan rekursi, tulisan ini tidak menekankan pada hal tersebut, tetapi pada eksplorasi kedua teknik penyelesaian. 2. ITERASI Untuk membandingkan iterasi dengan rekursi berikut sebuah contoh solusi iteratif untuk sebuah persoalan sederhana dalam aritmetika, yaitu operasi perkalian bilangan bulat (integer) yang diekspresikan sebagai aksi berulang dari penjumlahan dua buah bilangan bulat. Sebarang perkalian dua bilangan bulat aei, bei, dimana a>0, b>0, dapat dinyatakan sebagai: a x b

= a + a + a + ... v

+ a j

b buah Ekspresi di atas sesungguhnya ekivalen dengan penjumlahan b sebanyak a kali yang merupakan penjabaran dari ekspresi bxa. Dengan demikian untuk setiap ekpresi, baik axb maupun bxa, terdapat pemaknaannya (meaning) sendiri. Dalam terminologi konstruk pengulangan penyelesaian di atas membutuhkan inisialisasi sebuah nama informasi bertipe sama, sebut saja sum, yang digunakan untuk menampung hasil penjumlahan. Sebelum penjumlahan dilakukan nilai inisial dari peubah dimaksud adalah nol. Dapat ditunjukkan bahwa nilai inisial inilah yang paling natural dibanding nilai inisial lainnya. Pada iterasi pertama nilai peubah akan berubah dari nol menjadi a. Pada iterasi berikutnya, nilai peubah akan bertambah sebesar a. Dengan demikian, ide utama dari satu iterasi ialah bahwa nilai sum yang baru adalah nilai sum lama ditambah dengan a. Formulasi untuk hubungan matematik ini diekspresikan sebagai berikut: sum <— sum + a

12 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 11-19

Iterasi yang benar, terlepas dari aksi yang dikerjakan, berlangsung sebanyak hingga kali. Iterasi yang tidak bisa dijamin berhenti suatu saat dapat menyebabkan status eksekusi tidak terdefinisi. Salah satu contohnya adalah pengulangan abadi [forever loop). Dalam persoalan di atas, harus dijamin sedemikian rupa bahwa iterasi akan tepat berhenti setelah berlangsung b kali. Untuk mengendalikan banyak iterasi dibutuhkan satu nama informasi lain dengan tipe yang sama dengan b, namakan saja sebagai n b i t e r . Menggunakan konstruktor pengulangan w h i l e - d o penyelesaian persoalan di atas diberikan sebagai berikut: Program PerkalianSkalarl {versi iterasi dengan while-dol (Program ini mengkomputasi perkalian axb sebagai penjumlahan a dengan dirinya sedemikian rupa sehingga terdapat sebanyak b suku a) Kamus: a,b : integer nbiter : integer (pengendali iterasi) sum : integer (penampung hasil penjumlahan) Algcritma: input(a,b) (baca nilai a dan b dari pemakail s urn <— 0 nbiter <- 0 while nbiter < b do sum <— sum + a nbiter <- nbiter + 1 {invarian: nbiter > = b, sum=a+a+...a, terdapat sebanyak b suku a( output(sum)

Penyelesaian yang sama dengan konstruktor i t e r a t e tampak lebih sederhana. Program PerkalianSkalar2 (versi iterasi dengan iterate/ (Program ini mengkomputasi perkalian axb sebagai penjumlahan a dengan dirinya sedemikian rupa sehingga terdapat sebanyak b suku a} Kamus : a,b : integer nbiter : integer (pengendali iterasi} sum : integer (penampung hasil penjumlahan) Algcritma: input(a,b) (baca nilai a dan b dari pemakai) s urn <— 0 rib 11 e r <— 0 nbIter iterate 1. . b sum <— sum + a output (sum)

Penggunaan konstruktor i t e r a t e bagi penyelesaian persoalan diatas dinilai sangat tepat atas dasar pertimbangan bahwa banyak iterasi yang dilakukan terdefinisi dan pertambahan nilai pengendali iterasi beraturan. Sekalipun dalam solusi versi w h i l e - d o kedua hal itupun dipenuhi, tetapi sasaran akhir komputasi jelas (obvious), sehingga tidak dibutuhkan introduksi pola aksi baru di tengah eksekusi aksi perulangan. Iterasi versus Rekursi: Sebuah Perbandingan (Aditya R. Mitra)

13

2. REKURSI Dalam kehidupan sehari-hari rekursi seumpama ujud clone (replika) dari manusia dengan perilaku yang tepat sama, mengerjakan hal yang sama untuk tujuan yang sama. Ilustrasi lain yang populer untuk rekursi adalah seperti halnya seseorang yang tengah menonton acara TV yang juga tengah menayangkan orang lain sedang menonton acara TV dalam situasi serupa. Definisi yang lebih formal dalam bidang komputasi menyatakan rekursi sebagai suatu cara untuk menentukan berlangsungnya sebuah proses dalam terminologi dirinya [4]. Definisi ini sendiri menjadi menarik karena rekursi didefinisikan secara rekursif. Penjelasan yang lebih praktis (dan juga lebih mudah dipahami) untuk rekursi adalah bahwa rekursi terjadi ketika sebuah fungsi atau prosedur memanggil dirinya [Fre]. Fungsi atau prosedur seperti ini disebut fungsi atau prosedur rekursif. Pada dasarnya, rekursi bekerja atas penyederhanaan instans {instance) proses, yaitu dari instans proses yang lebih rumit (complicated) ke dalam ekspresi yang lebih sederhana (simpler). Penyederhanaan dari instans proses yang lebih sederhana ini pada akhirya akan memimpin pada sebuah instans yang paling sederhana (bisa dikatakan bentuk yang primitif, atomik) yang tidak dapat disederhanakan lagi. Instans inilah yang akan dinyatakan secara eksplisit. Dalam penyelesaian persoalan secara rekursif bentuk yang lebih rumit disebut sebagai rekurens; sedangkan bentuk yang paling sederhana disebut basis. Rekurens merupakan aksi yang akan berulang secara rekursif selama kondisi basis belum dipenuhi. Basis sendiri adalah aksi primitif yang akan menghentikan rekursi dan menandai pengembalian hasil komputasinya ke fungsi (atau prosedur) yang memanggilnya untuk pertama kalinya. Secara bertahap kendali program dikembalikan dari fungsi (atau prosedur) di aras terdalam ke fungsi (atau prosedur) di aras lebih tinggi yang memanggilnya (invoke), satu aras per satu aras. Dengan cara inilah komputasi rekursif diselesaikan (completed) Hal penting yang perlu diamati ketika bekerja dengan rekursi adalah bahwa pendefinisian basis dan rekurens dengan tepat dan benar adalah sangat mendasar. Kegagalan mendefinisikan kedua hal ini sangat potensial menyebabkan program berada dalam status yang tidak diharapkan, seperti kendali program tidak pernah bisa dikembalikan ke fungsi (atau prosedur) yang memanggil fungsi (atau prosedur) sejenis. Solusi rekursif untuk contoh persoalan yang sama dikonstruksi dari ide berikut. Pada mulanya nilai a dan b terdefinisi. Jika satu nilai a telah dimemorisasi dalam penghitungan, maka banyak nilai a selebihnya yang hendak dijumlahkan adalah berkurang satu, yaitu b-L Dengan cara serupa, ambil satu a dari sebanyak b-2 buah a tersisa, maka kini tersisa b-2 buah a. Demikian seterusnya, hingga suatu saat tidak ada lagi a yang tersisa. Dalam kondisi ini nilai b adalah 0 yang menyebabkan terhentinya rekursi atau eksekusi aksi rekurens. Memorisasi nilai a dalam uraian di atas dimungkinkan lewat terbentuknya peubahpeubah lokal dalam setiap fungsi yang dipanggil di berbagai aras. Nilai tersebut akan diakumulasikan dengan lemparan nilai (value return) dari fungsi yang dipanggilnya, namakan saja fungsi ini sebagai k a l i . Di aras terdalam kondisi basis terpenuhi. Pada kondisi ini fungsi melempar nilai 0 yang akan dijumlahkan pada nilai 14 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 11-19

a yang dimemorisasi dalam sebuah peubah lokal terdefinisi dalam fungsi yang memanggilnya. Hasil penjumlahan ini kemudian dengan cara serupa akan dilempar lebih lanjut ke fungsi pemanggil yang lebih luar untuk ditambahkan dengan nilai a yang dimemorisasi di dalam tubuh fungsi tersebut. Jadi, komputasi sebenarnya baru berlangsung saat nilai-nilai lemparan dari fungsi yang lebih dalam ditangkap oleh fungsi pemanggilnya. Proses ini berlangsung hingga pada suatu saat sum menangkap hasil komputasi fungsi yang dipanggil di aras tertinggi atau cakupan terluar. Ilustrasi komputasi perkalian skalar ini dibenkan sebagai berikut: Ekspresi aksi yang berulang (pada kondisi rekurens)

___-

k a l i ( a ,b)

/ Fungsi di aras terluar

a + kali(a,b-l) a + kali(a,b-2) — a + kali(a,b-3) a + kali(a,1) a + kali(a,0)

=

= II II

a + a + 2a a + 3a

II II

a + (b-2)a = a + (b-l)a = ba {b buah a}

a

\

Basis

Lemparan nilai fungsi di aras terdalam (pada kondisi basis)

Untuk a-2 dan b=3, k a l i (a,b) dapat dituliskan sebagai berikut: kali(2,3)

= 2 +

kali(2,2) 2 + kali(2,1) 2 + kali(2,0! 0 2 + 0 2 + 2 = 2 + 4 = 6

Secara eksplisit kondisi basis dinyatakan sebagai: Jika b=0, inakii kembalikan 0

Sedangkan pernyataan untuk kondisi rekurens dituliskan sebagai berikut: Jika b>0, maka kembalikan a + kali(a,b-l)

Iterasi versus Rekursi: Sebuah Perbandingan (Aditya R. Mitra)

15

Notasi algoritmik dari solusi dimaksud adalah sebagai berikut: Program PerkalianSkalar3 {versi rekursi) (Program ini mengkomputasi perkalian axb sebagai penjumlahan a dengan dirinya sedemikian rupa sehingga terdapat sebanyak b suku a 1 Kamus: a,b : integer sum : integer {hasil penampung hasil perkalian) function kali(input opl, op2:integer) —»integer (fungsi ini mengkomputasi perkalian opl x op2 sebagai penjumlahan opl dengan dirinya sedemikian rupa sehingga terdapat sebanyak op2 suku opl) Algoritma: input(a,b) {baca nilai a dan b dari pemakai) sum <- 0 sum <— kali(a,b) output(sum) function kali(input opl,op2:integer) —>integer (fungsi ini mengkomputasi perkalian opl x op2 sebagai penjumlahan opl dengan dirinya sedemikian rupa sehingga terdapat sebanyak op2 suku opl basis : jika op2=0, kembalikan 0 rekurens: jika op2>0, kembalikan opl+kali(opl,op2-l) ) Kamus: Algoritma: if op2=0 then -> 0 else —» opl + kali(opl, op2-l)

4. ITERASI TIDAK SELALU LEBIH SEDERHANA Untuk persoalan tertentu, solusi rekursif merupakan pilihan yang lebih baik, kalau tidak bisa dikatakan, satu-satunya solusi yang mungkin diperoleh. Traversal elemen senarai berkait linier sederhana {linear linked list) dapat dilakukan menggunakan teknik iterasi. Tetapi pada simpul-simpul dari struktur pohon (free) biner (dan umumnya pohon n-air) penelusuran memerlukan enumerasi lengkap atas semua lintasan yang mungkin sebelum aksi efektif. Dengan teknik rekursi, dengan mengenal pola struktur pohonnya, penelusuran simpul-simpul pohon di aras lebih dalam dapat dilakukan dengan memeriksa kondisi-kondisi percabangan penelusuran yang didefinisikan. Lebih mendasar dari itu, struktur pohon biner, misalkan, didefinisikan secara rekursif. Sebagai contoh, sebuah pohon biner dengan akar A mempunyai subpohon kiri, L dan subpohon kanan R (Gambar 1). Masing-masing subpohon tersebut sesungguhnya adalah pohon biner juga, dimana subpohon L 16 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 11-19

mempunyai akar A. dengan subpohon kiri L, dan subpohon kanan R ; sedangkan subpohon kanan K mempunyai akar AR dengan subpohon kiri L, dan subpohon kanan R.. Berdasarkan pola ini, kondisi percabangan dalam penelusuran berupa pemeriksaan pada akar pohon untuk menentukan penelusuran berikutnya, apakah berlanjut pada subpohon kiri atau subpohon kanan. Definisi ini dilengkapi dengan sebuah basis yang menyatakan bahwa struktur kosong adalah pohon biner juga.

Gambar 1 Struktur pohon biner, dengan akar A dan subpohon L dan R

Secara intuitif, solusi traversal secara rekursif merupakan pilihan terbaik dengan mempertimbangkan keteraturan pola pohon yang ada. Sederhananya bentuk prosedur penelusuran (sebagai contoh penelusuran secara preorder dan postorder) seperti didefinisikan untuk struktur pohon biner berelemen bilangan bulat berikut akan diperbandingkan secara kontras dengan solusi versi nonrekursifnya. type akar:integer type P tr Pohon Tpohon type pot" on:

procedure preOrder (input P:pohon) (menuliskan nilai- lilai simpul dari pohon

P secara

preorder)

Kamus: Algoritma: if P<>Nil then output(Pt.A) preorder(PT.L) preorder(PT.R)

ftulis nilai akar ke layar) fkunjungi subpohon kiri) (kunjungi

.•jubpohon

procedure postOrc er input P:pohon) {menuliskan nilai -ni lai simpul dari

kanan)

pohon P

secara pos tOi der)

Kamus: Algoritma:

if P O N i l then postOrder(Pt. L) postOrder(Pt. R) output(Pt.A)

(kunjungi subpohon kiri) (kunjungi subpohon kanan) (tulis ni Lai akar ke layar)

Iterasi versus Rekursi: Sebuah Perbandingan (Aditya R. Mitra)

17

Secara khusus, solusi rekursif penelusuran preorder akan dibandingkan {contrast) dengan versi nonrekursifnya. Untuk mendukung iterasi, digunakan sebuah struktur tumpukan (stack) yang akan menampung nilai-nilai dari simpul pohon yang akan ditelusuri. Penampungan ini bersifat sementara. pn icedure ] »i e< )rd< ir2 ( Lnj iut P:pohi n) {menuliskan nilai-nilai simpul dari pohon P secara preOrder;sebuah penelusuran secara preorder versi nonrekursif) Kamus: constant MaxEl:integer=100 type stack: function isEmpty(input S:stack) —^boolean procedure push(input/output S:Stack,input T:ptrPohon) function pop (input/output S:Stack) —>ptrPohon S : stack T:ptrPohon Algoritma: T <- P S.top <— 0 (stack kosong) repeat if T Q N i l then while T Q N i l do

output(ft.A) push(S,T) T <- TT.L if not empty(S) then T <- pop(S) T *- TT.R until (empty(S) and T=Nil)

Solusi versi nonrekursif tampak membutuhkan operasi yang lebih banyak untuk penelusuran pohon sehubungan dengan digunakannya struktur tumpukan untuk penampungan sementara. Secara garis besar, skema kerja kedua versi serupa, yaitu pencetakan nilai akar dilakukan segera setiap kali dijumpai pohon tak kosong diikuti dengan penelusuran sejauh-jauhnya pada subpohon kiri lalu subpohon kanan. Kesulitan dalam pembentukan solusi nonrekursif adalah menjamin bahwa nilai dari akar yang telah dikunjungi tidak boleh tercetak kembali. Selain itu, sekalipun nilai suatu simpul telah dicetak, tetapi alamatnya masih dibutuhkan untuk penelusuran pada kedua subpohonnya. Dapat dikatakan bahwa upaya yang dibutuhkan untuk menyusun algoritma penelusuran preorder versi nonrekursif tidak lebih ringan ketimbang versi rekursifnya. Contoh ini menggugurkan pendapat bahwa algoritma rekursif adalah lebih kompleks, selain juga lebih lambat. Dari segi kecepatan eksekusi versi rekursif (seharusnya) mempunyai performansi yang lebih baik Digunakannya tumpukan pada solusi nonrekursif menyebabkan sejumlah pemanggilan fungsi/prosedur primitif (empty, push, dan pop) secara intensif. 5. KESIMPULAN Pertimbangan penggunaan iterasi atau rekursi di dalam penyelesaian persoalan repetitif tidak cukup didasarkan hanya pada rasa (taste) semata. Pertimbangan dimaksud seharusnya memiliki dasar yang lebih baik dan elegan. 18 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 11-19

Dalam beberapa situasi, iterasi lebih tepat digunakan ketimbang rekursi. Sebaliknya, dalam situasi yang berbeda, penyelesaian rekursif merupakan solusi terbaik yang dapat diperoleh. Tambahan, kompleksitas dan kemungkinan program memasuki situasi tidak diharapkan {unexpected situation) merupakan pertimbangan lain bagi pemilihan kakas dimaksud. Sebagai implikasi dari pendefmisian rekursi, sebarang rekursi tidak dapat berlangsung tanpa melalui pemanggilan terhadap fungsi (atau prosedur) yang mengakomodasi atau merepresentasi aksi rekursi tersebut. Fungsi (atau prosedur) inilah yang menjadi pembatas dari kelakuan replikasi (clone) yang seharusnya terkendali sedemikian rupa sehingga suatu saat setiap replika dari yang terdalam/terakhir akan melempar nilai (atau memberi efek neto) terdefinisi yang menyebabkan rekursi akan berhenti (completed). Beberapa bahasa pemrograman (dalam paradigma pemrograman yang berbeda) mengenal rekursi dan tidak mendukung konsep iterasi. Sebagai konsekuensinya, iterasi diekspresikan sebagai bentuk derivasi dari pemahaman rekursi. Hal ini biasanya dikaji sebagai aspek prosedural dalam bahasa pemrograman yang mengacu pada paradigma pemrograman selain prosedural/imperatif. Daftar Pustaka [1] A. Tenenbaum, Y. Langsam, M. Augenstein, "Data Structure Using C", NewDelhi: PHI, 1995 [21 http://computing-dictionarv.thefreedictionary.com/recursion [3] http://www.mapfree.com/sbf/tips/recurs.html [4] http://www.wordiq.com/definition/Recursion

Iterasi versus Rekursi: Sebuah Perbandingan (Aditya R. Mitra)

19