algoritma rekrusif fibbonacci

5
ALGORITMA REKURSIF Rekursif sendiri adalah suatu fungsi yang 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 sendiri sering digunakan dalam perhitungan matematika, seperti untuk mencari faktorial, menghitung permutasi, kombinasi dan menghitung bilangan fibonacci. Algoritma rekursif ini langsung mengimplementasikan definisi rekursif bilangan fibonacci dalam bentuk fungsi rekursif. Contoh fungsi fibonacci : Analisis Dari fungsi rekursif di atas, bisa dilihat bahwa T(0) dan T(1) bernilai 1 karena jika inputnya 0 atau 1, program akan melakukan 1 proses yaitu assignment (permberian nilai). T(n) bernilai T(n-1) + T(n-2) + 1 karena di setiap tahap rekurens, program akan memanggil fibo(n-1) yang memiliki kompleksitas T(n-1) dan fibo(n-2) yang memiliki kompleksitas T(n-2), sementara itu untuk menjumlahkan keduanya dibutuhkan 1 proses. Oleh karena itu :

Upload: fazar-ikhwan-guntarra

Post on 17-Aug-2015

216 views

Category:

Documents


4 download

DESCRIPTION

algoritma

TRANSCRIPT

ALGORITMA REKURSIFRekursif sendiri adalah suatu fungsi yang memanggil dirinya sendiri. Dalam Rekursifsebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwarekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewatpemanggil prosedur dan fungsi.Rekursifsendiri sering digunakan dalamperhitunganmatematika, seperti untuk mencari faktorial, menghitung permutasi, kombinasi danmenghitung bilangan fibonacci.Algoritma rekursif ini langsung mengimplementasikan definisi rekursif bilanganfibonacci dalam bentuk fungsi rekursif. Contoh fungsi fibonacci :

Analisis Dari fungsi rekursif di atas, bisadilihat bahwaT!" danT#" bernilai #karena $ika inputnya ! atau #, programakan melakukan # proses yaitu assignmentpermberian nilai". Tn" bernilai Tn%#" & Tn%'" & # karena di setiap tahap rekurens, programakan memanggil fibon%#" yang memiliki kompleksitas Tn%#" dan fibon%'" yang memilikikompleksitas Tn%'", sementara itu untuk men$umlahkan keduanya dibutuhkan # proses. (lehkarena itu : )ika n*', Tn" * T#" & T!" & # * +, fn&'" * + )ika n*+, Tn" * T'" & T#" & # * ,, fn&'" * , )ika n*-, Tn" * T+" & T'" & # * ., fn&'" * / )ika n*,, Tn" * T-" & T+" & # * #,, fn&'" * #+ )ika n*0, Tn" * T," & T-" & # * ',, fn&'" * '# )ika n*1, Tn" * T0" & T," & # * -#, fn&'" * +- )ika n*/, Tn" * T1" & T0" & # * 01, fn&'" * ,,Dari situ bisa kita lihat bahwa Tn" akan berkembang secara eksponensial. 2ntuk mencarinotasi ( besarnya :Tn" 3 Tn%#"& Tn%#"& Tn%#" Tn" 3 +4Tn%#"5ehingga diperoleh Tn" * (+n". Algoritma ini adalah algoritma yang stabil, kompleksitasuntuk kasus terbaik sama dengan kompleksitas untuk kasus terburuknya.DERET FIBONACCIDeret 6ibonacci diperkenalkan pada tahun #'!' oleh 7eonardo dari Pisa yangdikenal sebagai 6ibonacci". Deret ini didefinisikan secara rekursif sebagai : fn" * fn%#" &fn%'" f!" * ! f#" * # 5ebenarnya terdapat 8ersi lain untuk f!" dan f#" yaitu f!" * #, f#" *#. 9amun dalam makalah ini, deret 6ibonacci yang digunakan adalah deret yang nilai f!" * !danf#" *#. 5elainitu, deret 6ibonacci yangdibahas pada makalahini adalahderet6ibonacci untuk indeks n bilangan bulat non negatif. Pen$elasan mengenai fungsi 6P: dan fungsi fibonacci yang $uga menggunakan fungsirekursif. :erikut merupakan source code program 6P: :#include #include using namespace std;int FPB(int x, int y);int main() {int !, ";cout