Awalnya kita harus mengetahui dulu apa itu rekursif.
- Pengertian Rekursif
Rekursif dapat diartikan bahwa suatu proses yang bisa memanggil dirinya sendiri. sedikit menyimpang dari pengertian ada sedikit pendapat tentang Rekursif salah satunya adalah 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.
- 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.
- 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.
dan ini sebagai contoh Algoritma beserta perhitunga dah hasil T(n)nya :
Judul : Algoritma Faktorial Secara Rekursif
Kamus :
x : integer
Algoritma :
//fungsi faktorial secara rekursif
function
pangkat(x:integer)
if x=0 then
faktorial <- 1
else
faktorial <- x * faktorial(x-1)
endif
endfunction
input x
output faktorial(x)
//untuk n=0 (best case)
t(n) = 0
//untuk n>0 (worst case)
t(n) = n * t(n-1)
t(n) = 1 + t(n-1)
= 2 + t(n-2)
= 3 + t(n-3)
= n + t(0)
jadi t(n) = n -> O(n)
Judul : Algoritma Pangkat Secara Rekursif
Kamus :
x,y : integer
Algoritma :
//fungsi pangkat secara rekursif
function
pangkat(x:integer, y:integer)
if y=0 then
pangkat <- 1
else
pangkat <- x * pangkat(x,y-1)
endif
endfunction
input x,y
output pangkat(x,y)
t(n) = 2n
Judul : Algoritma Perkalian Secara Rekursif
Kamus :
x,y : integer
Algoritma :
//fungsi perkalian secara rekursif
function
pangkat(x:integer, y:integer)
if y=0 then
kali <- 0
else
kali <- x + kali(x,y-1)
endif
endfunction
input x,y
output kali(x,y)
tn = n Operasi +
Tidak ada komentar:
Posting Komentar