Dua kali pemanggilan rekursi : Bilangan Fibonaci

Dua kali pemanggilan rekursi : Bilangan Fibonaci

Pada kasus-kasus sebelumnya, kita belajar tentang rekursif dengan satu dan
dua parameter. Kasus berikut ini melibatkan dua kali pemanggilan rekursif setiap
kali proses rekursif dilakukan.

Definisi :
Bilangan Fibonaci adalah bilangan berbentuk :
1, 1, 2, 3, 5, 8, 13, 21, ...
yaitu bilangan ke-n merupakan penjumlahan dari bilangan ke-(n-2) dan
bilangan ke-(n-1).
Bilangan fibonaci memang sejak awal sudah terdefinisi secara rekursif,
artinya suku ke-n baru bisa diketahui bila dua suku sebelumnya diketahui. Dengan
demikian implementasinya menjadi sederhana, yaitu mengikuti dari definisi di atas.

#include <iostream.h> int fibonaci(int n) { if ((n==1) || (n==2)) return 1; // kasus basis else return fibonaci(n-1) + fibonaci(n-2); // pemanggilan rekursif } void main(void) { cout << "fibonaci suku ke-10 = " << fibonaci(10) << endl; }

Macam-macam Metode Rekursi

Ada 3 macam rekursi yang lazim digunakan, yaitu :
1. rekursi menurun (going down recursion), artinya nilai dari parameter
berkurang mengarah ke kasus basis
2. rekursi menaik (going up recursion), artinya nilai dari parameter bertambah
mengarah ke kasus basis
3. rekursi dibagi separoh (two half recursion), artinya range atau jangkauan
dari parameternya dibagi menjadi dua bagian, setengah bagian pertama pada
pemanggilan pertama sedangkan setengah sisanya pada pemanggilan kedua.
Berikut ini adalah contoh kasus yang digunakan untuk menjelaskan ketiga
macam rekursi di atas. Kasus ini digunakan untuk menghitung nilai m2 + (m+1)2 + … +
n2. Implementasi juga menggunakan cara iteratif sebagai pembanding.

#include<iostream.h> template<class T> T Sum(T m, T n) { T tsum = 0; for (int i = m; i <= n; i++)

tsum += i*i; return tsum; } void main(void) { int a = 5, b = 10; cout << Sum(a,b) << endl; }

Di bawah ini diberikan program jumlah kuadrat dengan menggunakan cara going
down recursion.

#include<iostream.h> template<class T> T Sum(T m, T n) { if (m>=n) return n*n;

else
return Sum(m, n-1) + n*n;
}
void main(void)
{
int a = 5, b = 10;
cout << Sum(a,b) << endl;
}


Implementasi rekursi dengan cara menaik (going up recursion) diberikan di bawah
ini.
 

#include<iostream.h> template<class T> T Sum(T m, T n) { if (m>=n) return m*m;

else
return Sum(m+1, n) + m*m;
}
void main(void)
{
int a = 5, b = 10;
cout << Sum(a,b) << endl;
}



Pada kasus ketiga yaitu rekursi dibagi separoh, nilai di tengah dihitung dari
nilai tengah parameternya yaitu m + n dibagi 2. Oleh karena bisa terjadi nilai
setengahnya tidak selalu bulat, maka bisa diambil hanya nilai integernya saja.
Implementasi dari rekursi dibagi separoh disajikan berikut ini :

#include<iostream.h> template<class T> T Sum(T m, T n) { int tengah; if (m==n) return m*m; else {

tengah = (m+n) / 2;
return Sum(m, tengah) + Sum(tengah+1, n);
}
}
void main(void)
{
int a = 5, b = 10;
cout << Sum(a,b) << endl;
}
Kasus basisnya memang agak berbeda, yaitu m = n untuk lebih meyakinkan
bahwa nilai m2 akan diperoleh bila m = n (lebih eksplisit). Bila pada dua kasus
sebelumnya, pohon pemanggilan miring (ke kiri dan ke kanan) maka pohon
pemanggilan dengan cara rekursi dibagi separoh akan menjadi pohon yang seimbang
seperti berikut ini :