Fungsi Rekursif Untuk Mencari Deret Fibonacci

Dalam pelajaran matematika, bilangan Fibonacci adalah barisan yang didefinisikan sebagai berikut:

Persamaan F(n) dapat dijelaskan sebagai berikut :

Jika n=0, maka F(0)=0

Jika n=1, maka F(1)=1

Jika n>1 berlaku rumus F(n-1) + F(n-2)

Jika n=2, maka F(2-1) + F(2-2) = F(1) + F(0) = 1 + 0 = 1

Jika n=3 maka F(3-1) + F(3-2) = F(2) + F(1)  = 1 + 1 = 2

Jika n =4 maka F(4-1) + F(4-2) = F(3) + F(2) = 2 + 1 = 3

Dst

Hasil deret bilangan Fibonacci adalah :  0,1,1,2,3, dst

Kesimpulan :

Untuk n lebih besar dari 1, maka nilainya adalah merupakan hasil penjumlahan dari 2 bilangan yang ada di depannya. Dengan aturan ini, maka barisan bilangan Fibonaccci adalah sebagai berikut:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946... 

Untuk n >1, maka rumus F(n-1) + F(n-2) selalu digunakan ketika nilai n berubah. Karena itu, F(n-1) + F(n-2) dibuat menjadi sebuah fungsi. Ketika nilai n bertambah di dalam fungsi, maka nilai tersebut dikirim ke dalam fungsinya  dengan cara passing by value ketika memanggil dirinya sendiri.

            

Program C++ rekursif deret Fibonacci :

#include iostream.h

#include conio.h

int fibo(int n)

{

   if(n==0)

     return 0;

   else if(n==1)

     return 1;

   else

     //fungsi rekursif

     return fibo(n-1)+fibo(n-2);

}

int main()

{ clrscr();

  int bil;

  cout<<"\nFungsi Rekursif untuk mencari Bilangan Fibonacci ke-n"<

  cout<<"\nMasukkan bilangan suku ke-n = ";

  cin>>bil;

      //pemanggilan fungsi

  cout<<"Fibonacci("<

  getche();

  return 0;

}

Output program :

Program di atas hanya mencari suku ke-n dari deret Fibonacci.  Bagaimana jika kita ingin mencetak deret Fibonacci mulai suku pertama hingga suku ke-n?

Untuk mencetak deret ficonacci, maka kita harus mengirim nilai n mulai dari  0 hingga suku ke-n. Dalam program, suku ke-n dinyatakan dengan variable bil. Untuk mengirim  nilai n mulai dari 0 hingga bil, maka kita menggunakan perulangan for. Dengan perulangan for,  fungsi fibo akan dipanggil ketika nilai berubah dan hasil dikirim kembali ke fungsi main dan langsung dicetak.

Program untuk mencetak deret fobonacci adalah sebagai berikut :

#include iostream.h

#include conio.h

int fibo(int n)

{

   if(n==0)

     return 0;

   else if(n==1)

     return 1;

   else

     //fungsi rekursif

     return fibo(n-1)+fibo(n-2);

}

int main()

{ clrscr();

  int bil;

  cout<<"\nFungsi Rekursif untuk mencari deret Fibonacci"<

  cout<<"\nDeret Fibonacci hingga suku ke-n = ";

  cin>>bil;

  for (int n=0;n<=bil;n++)

     cout<

  getche();

  return 0;

}

Output program :

Demikian pembahasan tentang fungsi rekursif untuk mencari deter Fibonacci. Selamat belajar, semoga sukses selalu.