Rekursif
Salah
satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan
fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali.
Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi
pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika
yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang
memanggil dirinya sendiri.
Kode
berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari
dua bilangan:
def kali(a, b):
return a if b == 1 else a + kali(a, b - 1)
Bagaimana
cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil
perintaha + kali(a, b - 1),
yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b.
Mari kita coba panggil fungsi kali dan uraikan langkah
pemanggilannya:
kali(2, 4)
-> 2
+ kali(2, 3)
-> 2
+ (2 + kali(2, 2))
-> 2
+ (2 + (2 + kali(2, 1)))
-> 2
+ (2 + (2 + 2))
-> 2
+ (2 + 4)
-> 2
+ 6
-> 8
Perhatikan
bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi
rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti (2). Setelah menghilangkan semua pemanggilan fungsi,
penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling
terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk
melakukan perhitungan faktorial:
def faktorial(n):
return n if n == 1 else n * faktorial(n - 1)
Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali.
Mari kita panggil dan lihat langkah pemanggilannya:
faktorial(5)
-> 5
* faktorial(4)
-> 5
* (4 * faktorial(3))
-> 5
* (4 * (3 * faktorial(2)))
-> 5
* (4 * (3 * (2 * faktorial(1))))
-> 5
* (4 * (3 * (2 * 1)))
-> 5
* (4 * (3 * 2))
-> 5
* (4 * 6)
-> 5
* 24
->
120
Dengan
melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat melihat
bagaimana fungsi rekursif memiliki dua ciri khas:
1. Fungsi
rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut
berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak
tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang
berarti algoritma kita tidak benar.
2. Fungsi
rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan
data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama
dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut
menjadi masalah-masalah kecil.
Setiap
fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan
fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang
dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi
sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat
kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.
Rekursif
adalah salah satu metode dalam dunia matematika dimana definisi sebuah fungsi mengandung
fungsi itu sendiri.
Dalam dunia pemrograman, rekursi diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri
Dalam dunia pemrograman, rekursi diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri
n Contoh
fungsi rekursif misalnya adalah fungsi pangkat, faktorial, dan barisan
fibonacci.
n Dalam
fungsi pangkat xy , kita tahu bahwa semua bilangan selain 0, jika dipangkatkan
dengan 0 nilainya sama dengan 1. Jika x dipangkatkan dengan y, dengan y lebih
dari 0, maka hasilnya sama dengan x dikalikan dengan x dipangkatkan y – 1.
Jika dituliskan dalam
notasi matematika definisinya adalah sebagai berikut:
Kita
lihat di atas pada definisi y > 0, bentuk pemangkatan muncul kembali di sisi
kanan. Itulah yang disebut rekursif.
Definisi
rekursif selalu dimulai dengan kasus penyetop, penghenti, atau kasus dasar dari
suatu permasalahan, dalam hal ini terjadi ketika nilai y = 0.
Definisi
rekursif yang lebih kompleks mengandung inti dari permasalahan yang akan
dipecahkan, namun lebih sederhana. Dalam hal ini yang tadinya x dipangkatkan
dengan y, kini bentuk pemangkatan menjadi lebih sederhana, yaitu y – 1.
Hal
ini dimaksudkan untuk “menggiring” masalah kompleks ke kasus dasar atau
penyetop rekursinya.
Definisi
rekursif selalu dimulai dengan kasus penyetop, penghenti, atau kasus dasar dari
suatu permasalahan, dalam hal ini terjadi ketika nilai y = 0.
Definisi
rekursif yang lebih kompleks mengandung inti dari permasalahan yang akan
dipecahkan, namun lebih sederhana. Dalam hal ini yang tadinya x dipangkatkan
dengan y, kini bentuk pemangkatan menjadi lebih sederhana, yaitu y – 1.
Hal
ini dimaksudkan untuk “menggiring” masalah kompleks ke kasus dasar atau
penyetop rekursinya.
Ide dasar dalam
memecahkan suatu masalah dengan rekursif adalah sebagai berikut:
Mari kita lihat contoh
rekursif yang jauh lebih sederhana,Masalah yang akan dipecahkan adalah memotong
roti tawar tipis-tipis sampai habis. Jika masalah ini akan dipecahkan secara
rekursif, maka solusinya adalah:
1. Jika
roti sudah habis atau potongannya sudah
paling tipis, pemotongan roti selesai
2. Jika
roti masih bisa dipotong, potong tipis dari tepi roti tersebut, lalu lakukan
prosedur 1 dan 2 untuk sisa potongannya.
Contoh Program
program faktorial;
uses wincrt;
var
faktor :real;
i,n :integer;
begin
write('Masukkan bilangan n =');readln(n);
faktor:=1;
for i:= 2 to n do {Menghitung n faktorial}
faktor:=faktor*i;
writeln(n,' Faktorial = ',faktor:0:0);
end.
Hasil Program
Masukan Bilangan n = 3
3 Faktorial 6
Masukan Bilangan n = 2
2 Faktorial 1
Kita dapat menuliskan
fungsi penghitung factorial seperti dibawah ini
1. int Faktorial(int n)
2. {
3. if ((n == 0) || (n == 1 ))
4. return (1);
5. else
6. return (n * Faktorial(n-1));
7. }
n Pada
baris 3 dari fungsi diatas,
nilai n dicek sama dengan 0 atau 1,
jika ya, maka fungsi mengembalikan nilai 1 {baris 4},
jika tidak, fungsi mengembalikan nilai n * Faktorial (n -1)
{baris 6}
n disinilah
letak proses rekursif itu, perhatikan fungsi factorial ini memanggil dirinya
sendiri tetapi dengan parameter (n-1)
Barisan yang
didefinisikan secara rekursif
Contoh:
Barisan bilangan
pangkat dari 2
an = 2n
untuk n = 0, 1, 2, … .
Barisan ini dapat
didefinisikan secara rekursif:
a0 = 1
an+1 = 2an untuk n = 0, 1, 2, …
Langkah-langkah untuk
mendefinisikan barisan secara rekursif:
1. Langkah
basis: Spesifikasi anggota awal.
2. Langkah
rekursif: Berikan aturan untuk membangun anggota baru dari anggota yang telah
ada.
Contoh barisan yang
didefinisikan
secara rekursif
secara rekursif
Berikan definisi
rekursif dari an=rn, dengan rÎN,
r≠0 dan n bilangan bulat positif.
Solusi:
Definisikan a0=r0=1
dan an+1=r
. an untuk n = 0, 1, 2, …
n Contoh:
definisi rekursif himpunan Ekspresi Aritmatika EA
n Basis: 1,
2, 3, 4, 5 Î EA
n Rekursif: jika a Î
EA
dan b Î EA, maka
n a + b Î EA
n a – b Î EA
n a ´
b Î EA
n a ¸
b Î EA
Rekursif berarti bahwa suatu
proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf,
Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam
Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya
adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan
fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan
teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung
keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke
dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan
akan berakhir.
Contoh paling sederhana dari proses rekursif ini adalah proses menghitung nilai
factorial dari suatu bilangan bulat positif dan mencari deret Fibbonacci dari
suatu bilangan bulat.
1. Nilai
factorial secara rekursif dapat ditulis sebagai
0 ! = 1
N ! = N x (N-1) !
yang secara pemrograman dapat
ditulis sebagai
Faktorial(0) = 1
(1)
Faktorial(N) = N*Faktorial(N-1)
(2)
Persamaan (2) di atas adalah
contoh hubungan rekurens (recurrence relation), yang berarti bahwa nilai
suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan
argumen yang lebih kecil. Persamaan (1) tidak bersifat rekursif, disebut nilai
awal atau basis. Setiap fungsi rekursif paling sedikit mempunyai satu
nilai awal, jika tidak fungsi tersebut tidak bisa dihitung secara eksplisit.
2. Bilangan
Fibbonacci didefinisikan sebagai berikut
1
1 2 3 5
8 13 21
34 55 89 …
dari barisan tersebut dapat
dilihat bahwa bilangan ke-N (N>2) dalam barisan dapat dicari dari dua
bilangan sebelumnya yang terdekat dengan bilangan N, yaitu bilangan ke-(N-1)
dan bilangan ke-(N-2), sehingga dapat dirumuskan sebagai
Fibbonacci(1) = 1
(1)
Fibbonacci(2) = 1
(2)
Fibbonacci(N) = Fibbonacci(N-1)
+ Fibbonacci(N-2) (3)
Dengan persamaan (1) dan (2) adalah basis dan persamaan (3) adalah rekurensnya
Rekursif Versus Iteratif
Dalam beberapa situasi, pemecahan secara rekursif maupun secara iteratif
mempunyai keuntungan dan kekurangan yang bisa saling diperbandingkan. Adalah
cukup sulit untuk menentukan mana yang paling sederhana, paling jelas, paling
efisien dan paling mudah disbanding yang lain. Boleh dikatakan pemilihan cara
iterative maupun rekursif merupakan kesenangan seorang programmer dan
tergantung konteks permasalahan yang akan dipecahkan sesuai dengan kesanggupan
yang bersangkutan.
Perhatikanlah contoh berikut
:
Contoh 1.
function FACT(N : integer) ® integer
{mengirimkan bilangan factorial dengan cara
rekursif}
Deklarasi
Deskripsi
if (N=0) then
return 1
{Basis}
else
return(N*FACT(N-1))
{Rekurens}
endif
Contoh 2.
function FIBO(N : integer) ® integer
{mengirimkan bilangan fibbonacci dengan cara
rekursif}
Deklarasi
Deskripsi
if ((N=1) or (N=2)) then
return 1
{Basis}
else
return(FIBO(N-1)+
FIBO(N-2)) {Rekurens}
endif
Contoh 3.
function FACT(N : integer) ® integer
{mengirimkan bilangan factorial dengan cara
iteratif}
Deklarasi
x,i : integer
Deskripsi
x ¬ 1
for i = 1 to N do
x ¬ i*x
endfor
return x
Contoh 4.
function FIBO(N : integer) ® integer
{mengirimkan bilangan fibbonacci dengan cara
iteratif}
Deklarasi
Fibbonacci, Akhir, Bantu, i : integer
Deskripsi
If N=0 then
return 0
else
i¬1
Fibbonacci ¬1
Akhir ¬0
while (i¹N)do
Bantu ¬ Fibbonacci
i ¬ i + 1
Fibbonacci ¬ Fibbonacci + Akhir
Akhir ¬ Bantu
Endwhile
return Fibbonacci
endif
Contoh program
