Deret Fibonacci / Fibonacci Squence

Deret fibonacci mempunyai suku bilangan bulat dimana masing-masing nilai suku bilangan tersebut merupakan hasil penjumlahan dari 2 nilai suku sebelumnya.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ……..

Deret fibonacci mempunyai definisi rekursif sebagai berikut :

• Jika n < 2, maka fibo(n) = n
• Jika n >= 2, maka fibo(n) = fibo ( n-2 ) + fibo ( n-1)

 

Deret fibonacci tersebut dapat diimplementasikan kedalam program dibawah ini :

 

Uses Wincrt;

Function fibo ( n : integer ) ; longint ;

Begin

            If ( n = 0 ) or ( n = 1 ) then

                        Fibo := n

                 Else

                        Fibo := fibo (n -2) + Fibo ( n-1) ;

End;

begin

Writeln( fibo (5) );

End.

 

Program diatas merupakan contoh apabila kita ingin menghitung nilai fibonacci 5.

Apabila kita buktikan dengan perhitungan, maka proses penghitungannya adalah sbb :

 Fibo 5 =  fibo (3) + fibo (4)

            =  fibo (1) + fibo(2) + fibo (4)

            =  1 + fibo (0) + fibo (1) Fibo (4)

            =  1 + 0 + 1 + fibo (2) fibo (3)

            =  2 + fibo (0) + fibo (1) + fibo (3)

            =  2 + 0 + 1 + fibo (1) + fibo (2)

            =  3+ 1 + fibo (0) fibo (1)

            =  4 + 0 + 1

            =  5

           

Deret fibonacci termasuk kedalam algoritma rekursif. Rekursif  merupakan proses dari sub program yang dapat berupa procedure atau fungsi yang dapat memanggil dirinya sendiri.

Namun rekusif mempunyai kelemahan yaitu suatu proses yang sudah selesai di proses akan diproses ulang kembali sehingga akan membuat program menjadi lama, karena setiap kali subprogram dipanggail maka diperluakan sejumlah tambahan memori.

 

Untuk membuktikan kelemahan tersebut kita bisa mencoba dengan program untuk menghitung nilai fibonacci dengan 2 digit angka atau lebih besar dari itu, maka ketika program tersebut di running proses akan lama.

 

 

 

 

 

 

S : Logika Dan Algoritma/ Arif B.P