Rekursi

Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer. Konsep
ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan
yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do.
Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan
dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk
mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma
tersebut mudah untuk dianalisa.

Rekursi Dasar
Rekursi mempunyai arti suatu proses yang bias memanggil dirinya sendiri. Dalam
sebuah rekursi sebenarnya tekandung pengertian sebuah prosedur atau fungsi.
Perbedaannya adalah bahwa rekursi bisa memanggil dirinya sendiri, kalau prosedur atau
fungsi harus diipanggil melalui pemanggil prosedur atau fungsi.
Untuk memulai bahasan rekursi, kita membahas sebuah masalah sederhana yang
kemungkinan kita tidak berpikir untuk menyelesaikan dengan cara rekursif. Yaitu
permasalahan faktorial, yang mana kita menghitung hasil faktorial dari sebuah bilangan,
yaitu n. Faktorial dari n (ditulis n!), adalah hasil kali dari bilangan tersebut dengan
bilangan di bawahnya, di bawahnya hingga bilangan 1. Sebagai contoh, 4! = (4)(3)(2)(1).
Salah satu cara untuk menghitung adalah dengan menggunakan loop, yang mengalikan
masing-masing bilangan dengan hasil sebelumnya. Penyelesaian dengan cara ini
dinamakan iteratif, yang mana secara umum dapat didefinisikan sebagai berikut:
39
n! = (n)(n-1)(n-2) … (1)
Cara lain untuk menyelesaikan permasalahan di atas adalah dengan cara rekursi, dimana
n! adalah hasil kali dari n dengan (n-1)!. Untuk menyelesaikan (n-1)! adalah sama
dengan n!, sehingga (n-1)! adalah n-1dikalikan dengan (n-2)!, dan (n-2)! adalah n-2
dikalikan dengan (n-3)! dan seterusnya sampai dengan n = 1, kita menghentikan
penghitungan n! Cara rekursif untuk permasalahan ini, secara umum dapat kita detailkan
sebagai berikut:
1 jika n=0, n=1
F(n) =
nF(n-1) jika n>1
Pada Gambar 5.1 dibawah ini digambarkan penghitungan 4! dengan menerapkan
konsep rekursi. Dalam gambar tersebut juga digambarkan dua fase dasar dari sebuah
proses rekursi: fase awal dan fase balik. Dalam fase awal, masing-masing proses
memanggil dirinya sendiri. Fase awal ini berhenti ketika pemanggilan telah mencapai
kondisi terminal. Sebuah kondisi teminate adalah kondisi dimana sebuah fungsi rekursi
kembali dari pemanggilan, artinya fungsi tersebut sudah tidak memanggil dirinya sendiri
dan kembali pada sebuah nilai. Sebagai contoh, dalam penghitungan faktorial dari n,
kondisi terminal adalah n = 1, n = 0. Untuk setiap fungsi rekursi, minimal harus ada satu
kondisi terminal. Setelah fase awal selesai, kemudian proses melanjutkan pada fase balik,
dimana fungsi sebelumnya akan dikunjungi lagi dalam fase balik ini. Fase ini berlanjut
sampai pemanggilan awal, hingga secara lengkap proses telah berjalan.
Gambar 5.1 Proses Komputasi Secara Rekursif dari 4!
F(4)=4x F(3) fase awal
F(3)=3x F(2) .
F(2)=2x F(1) .
F(1)=1 kondisi terminal
F(2)=(2)x(1) fase balik
F(3)=(3)x(2) .
F(4)=(4)x (6) .
24 rekursi lengkap
40
Dalam Program 5.1 ditampilkan sebuah fungsi dalam C, fact_rec, dengan
parameter sebuah bilangan n dan menghitung faktorial secara rekursi. Fungsi tersebut
bekerja sebagai berikut. Jika n kurang dari 0, maka fungsi kembali ke 0, menunjukkan
kesalahan. Jika n = 0 atau 1, fungsi kembali ke 1 karena 0! dan 1! hasilnya 1. Dan ini
adalah kondisi terminal. Selainnya itu, fungsi kembali dengan hasil n kali factorial dari n-1.
Faktorial dari n-1 adalah penghitungan kembali secara rekursif dengan memanggil fact
lagi. Perhatikan persamaan dari definisi rekursi dengan implementasi di bawah ini.
int fact_rec(int n)
{
/************************************************************
* Menghitung sebuah faktorial secara rekursif *
************************************************************/
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return n * fact(n-1);
}
Referensi : lecturer.eepis-its.edu/.../Data%20Structure%20-%20Bab%205.pdf