Rekursif ialah salah satu teknik pemrograman dengan cara memanggil sebuah fungsi dari dirinya sendiri, baik itu secara langsung maupun tidak langsung. Pemanggilan fungsi rekursif secara langsung berarti dalam fungsi tersebut terdapat statement untuk memanggil dirinya sendiri sedangkan secara tidak langsung berarti fungsi rekursif tersebut memanggil 1 atau lebih fungsi lain sebelum memanggil dirinya sendiri.
[ret-val] coba([parameter])
{
// statement
coba([parameter])
// statement
}
Rekursif tidak selalu lebih jelek daripada iteratif . Ada kalanya sebuah fungsi rekursif justru mempermudah penyelesaian masalah yang ditemui pada kasus iteratif (pengulangan) Kelemahan pada proses rekursif antar lain, memerlukan tempat penampungan stack yang cukup besar. Karena setiap kali pemanggilan fungsi , register – register seperti cs ( untuk memory far ) dan ip harus disimpan , belum lagi untuk penanganan local variable serta parameter fungsi yang tentunya membutuhkan ruang untuk stack lebih banyak lagi. Selain itu karena setiap pemanggilan fungsi , register dan memory harus di push ke stack maka setelah selesai pemanggilan perlu diadakannya pop stack untuk mengembalikan memory dan register kembali ke keadaan awal , ini sering disebut sebagai overhead.
proses rekrusif.
kali ini saya menggunakan pseudocode dulu.
Misalkan Fungsi tersebut dipanggil dengan nilai a = 3 dan b = 3 maka pertama tama di cek
apakah b = 0 (if (b == 0) return), jika sama maka keluar. Ternyata nilai b tidak sama dengan 0 maka tambahkan a dengan 1 dan kurangi b dengan 1 . Maka keadaan sekarang menjadi a = 4 dan b = 2 . Baris berikutnya menampilkan nilai a dan b ke layar (printf("Masuk -> a = %d || b = %d \n",a,b)). Kemudian panggil fungsi rekursi dengan nilai a = 4 dan b = 2 . Langkah – langkah tersebut diulang terus sampai pemanggilan fungsi rekursi dengan nilai a = 6 dan b = 0. Pada saat ini kondisi if bernilai benar sehingga fungsi akan keluar (return) dan melanjutkan perintah setelah pemanggilan Fungsi rekursi dengan a = 6 dan b = 0. Yaitu mencetak nilai a dan b (printf("Keluar = %d || b = %d \n",a,b)).
void rekursi(int a,int b)
{
if (b == 0) return;
a++;
b--;
printf("Masuk -> a = %d || b = %d \n",a,b);
rekursi(a,b);
printf("Keluar -> a = %d || b = %d \n",a,b);
}
Setelah mencetak nilai a dan b maka fungsi rekursif akan keluar lagi , dan melanjutkan perintah setelah pemanggilan fungsi rekursif sebelumnya dimana nilai a = 5 dan b = 1 . Demikian seterusnya sampai nilai a = 4 dan nilai b = 2. yang tidak lain pemanggilan fungsi rekurif yang pertama. Proses pemanggilan fungsi rekursif dapat diilustrasikan :
Langkah ke :
1. a = 4 ; b = 2 . Cetak : Masuk -> a = 4 || b = 2
2. a = 5 ; b = 1 . Cetak : Masuk -> a = 5 || b = 1
3. a = 6 ; b = 0 . Cetak : Masuk -> a = 6 || b = 0
4. a = 6 ; b = 0 , Cetak : Keluar -> a = 6 || b = 0
5. a = 5 ; b = 1 , Cetak : Keluar -> a = 5 || b = 1
6. a = 4 ; b = 2 , Cetak : Keluar -> a = 4 || b = 2
Menghitung Nilai Faktorial dan Fibonacci Dengan Rekursif dengan bahasa C
Untuk menghitung nilai faktorial bilangan bulat positif marilah kita daftarkan dulu nilai – nilai faktorial untuk mempermudah pengambilan algoritma .
0! = 1
1! = 1
2! = 2 x 1 algoritma N! = N x (N – 1) !
3! = 3 x 2 x 1 = 3 x 2!
4! = 4 x 3 x 2 x 1 = 4 x 3!
Nah dari daftar diatas dapat dibuat fungsi rekursi untuk menghitung nilai faktorial ke n yaitu
Fak(n)= n > 1 --> n * Fak(n-1), n == 0 and n == 1 --> 1
implemntasi dalam bahasa C
int Fakt(int n)
{
if (n == 1 || n == 0) return 1;
return n * Fakt(n-1);
}
Untuk Mencari Bilangan Fibonacci juga sama . Sebelumnya mari kita daftarkan dulu bilangan Fibonacci untuk mempermudah pencarian algoritma .
1 1 2 3 5 8 13 ...
Dapat dilihat bahwa
Fibo(0) = 1
Fibo(1) = 1
Fibo(2) = Fibo(1) + Fibo(0) = 1 + 1 = 2
Fibo(3) = Fibo(2) + Fibo(1) = 2 + 1 = 3
Maka akan didapat rumusan untuk bilangan Fibonacci berupa :
Fibo(n)= n > 1 --> n * Fibo(n-1) + Fibo(n-2) , n == 0 and n == 1 --> 1.
met nyoba ya. maaf kalau ada salah tulis mohon di benarkan.
