Deretan Fibonacci, Iteratif & Rekursif

Kebetulan pagi-pagi ada yang nanya gw soal gimana cara ngerjain program deretan Fibonacci. Sebenernya sih bahasannya mirip dengan waktu gw ngebahas faktorial beberapa waktu yang lalu, cuma kasusnya sedikit lebih ribet. Deretan Fibonacci ini bentuknya kayak begini.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Di atas ini gw ngasih deretan Fibonacci mulai dari bilangan pertama sampe bilangan kesepuluh. Di deretan Fibonacci ini bilangan pertama & keduanya udah pasti nilainya 1, untuk bilangan ketiga & seterusnya dipakai rumus ini.

F(n) = F(n-1) + F(n-2)

F(n) nilai bilangan ke-n di deretan Fibonacci
F(n-1) nilai bilangan ke-(n-1) di deretan Fibonacci
F(n-2) nilai bilangan ke-(n-2) di deretan Fibonacci

Jadi bilangan ketiga sama dengan bilangan pertama ditambah bilangan kedua, bilangan keempat sama dengan bilangan kedua ditambah bilangan ketiga, bilangan kelima sama dengan bilangan ketiga ditambah bilangan keempat, & seterusnya sampe bilangan ke-n.

Nah, sekarang gimana kalo itu dibuat jadi program? Dari bentuk rumusnya sih udah keliatan kalo deretan Fibonacci ini lebih gampang dibikin programnya pake fungsi rekursif. Tapi gimana kalo harus pake cara iteratif? Masalahnya sih tadi itu gw ditanyain buat tugas kuliah, & materi kuliahnya belum sampe ke fungsi rekursif. Jadi dikerjainnya harus pake cara yang udah diajarin, kalo begini ya mau nggak mau harus bikin versi iteratifnya dulu. Function yang dipake nanti bentuknya kayak begini buat versi iteratifnya.

int iterativeFibo (int n)
{
if (n == 1 || n == 2)
return 1;
else
{
int f1 = 1;
int f2 = 1;

int fn;

for (int i = 3; i <= n; i++)
{
fn = f1 + f2;
f1 = f2;
f2 = fn;
}

return fn;
}
}

Variabel f1 & f2 gw pake buat nyimpen nilai bilangan di posisi n-1 & n-2, variabel fn gw pake buat nyimpen nilai bilangan di posisi n di deretan Fibonacci. Looping for-nya gw pake mulai dari nilai n=3, soalnya untuk nilai n=1 & n=2 udah ditangani perintah if. Jadi kalo nilai n yang diinput 3 atau lebih programnya bisa langsung mulai loopingnya dari angka 3, nggak perlu lagi ngitung untuk posisi n=1 & n=2. Lagian nilai untuk posisi n=1 & n=2 udah diset di variabel f1 & f2, jadi mulai dari n=3 kita bisa langsung ngitung pake rumus di atas tadi.

Di dalam looping for itu, nilai f1 & f2 bakal diganti dengan nilai bilangan di posisi n-1 & n-2 untuk posisi n=i, jadi perhitungan nilai fn bisa terus dihitung pake penjumlahan nilai variabel f1 & f2. Kalo loopnya udah selesai, function ini bakal ngembaliin nilai fn.

Untuk fungsi rekursifnya sendiri sih pendek banget, bener-bener persis sama dengan rumus yang gw kasih di awal post tadi.

int recursiveFibo (int n)
{
if (n == 1 || n == 2)
return 1;
else
return recursiveFibo(n-1) + recursiveFibo(n-2);
}

Miris juga sih kalo function yang isinya bisa dibikin cuma pake 4 baris aja harus ditulis panjang-panjang pake cara iteratif tadi. Tapi ya, dosen jangan dilawan lah ya.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s