Untuk dapat memahami proses yang terjadi dalam sebuah fungsi rekursif , perhatikan contoh fungsi rekursif berikut : voidrekursi(inta,intb) { If(b==0)return; a++; b‐‐; cout<<"Masuk\n"<<a<<b; rekursi(a,b); cout<<"Keluar\n"<<a<<b; } 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 cout<<"Masuk \ 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 (cout<<"Keluar \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:
Langkahke: Rekursif(3,3)1a=4;b=2.Cetak:masuka=4||b=2 162a=5;b=1.Cetak:masuka=5||b=1 Rekursif(4,2)3a=6;b=0.Cetak:masuka=6||b=0 254a=6;b=0.Cetak:keluara=6||b=0 Rekursif(5,1)5a=5;b=1.Cetak:keluara=5||b=1 346a=4;b=2.Cetak:keluara=4||b=2 Rekursif(6,0)
Gambar 10.1. Proses Pemanggilan Fungsi Rekursif
Penggunaan fungsi rekursif misalnya pada fungsi pangkat, faktorial, dan barisan fibonacci. Mari kita lihat satu demi satu. Dalam fungsi pangkat xy , kita tahu bahwa semua bilangan selain 0, jika dipangkatkan dengan 0 nilainya sama dengan 1. Jika x dipangkatkan dengan y, dengan y lebih dari 0, maka hasilnya sama dengan x dikalikan dengan x dipangkatkan y – 1. Jika dituliskan dalam notasi matematika definisinya adalah sebagai berikut: Kita lihat di atas pada definisi y > 0, bentuk pemangkatan muncul kembali di sisi kanan. Itulah yang disebut rekursif. Definisi rekursif selalu dimulai dengan kasus penyetop, penghenti, atau kasus dasar dari suatu permasalahan, dalam hal ini terjadi ketika nilai y = 0. Definisi rekursif yang lebih kompleks mengandung inti dari permasalahan yang akan dipecahkan, namun lebih sederhana. Dalam hal ini yang tadinya x dipangkatkan dengan y, kini bentuk pemangkatan menjadi lebih sederhana, yaitu y – 1. Hal ini dimaksudkan untuk “menggiring” masalah kompleks ke kasus dasar atau penyetop rekursinya. Untuk x = 10 dan y = 0, hasil dari xy adalah 1. Untuk x = 10 dan y = 3 hasilnya dapat digambarkan sebagai berikut: Konsep rekursifitas banyak ditemui di dunia nyata. Istilah ini muncul pertama kali di kajian bidang matematika. Dalam kasus tertentu, konsep ini memudahkan perumusan formula. Konsep ini pun difasilitasi dalam pemrograman. Dalam pemrograman, ada 2 terminologi yang bisa didefinisikan dengan rekursif, yaitu prosedur dan fungsi. Seperti halnya dalam bidang matematika, penggunaan konsep ini juga untuk memudahkan pendefinisian dua terminologi tersebut. Bahkan terdapat suatu masalah yang hanya bisa diselesaikan dengan rekursifitas dan sangat sulit untuk diselesaikan tanpa rekursifitas. Definisi rekursif harus memuat komponen basis dan komponen rekursif. Dalam pemrograman, komponen ini dapat dipisahkan dengan menggunakan perintah analisa kasus. Misalkan e1 adalah ekspresi kondisi untuk basis dan e2 adalah ekspresi kondisi untuk bagian rekursif, definisi rekursif dapat dituliskan: if(e1)then {bagianbasis} else {bagianrekursif} Salah satu contoh dari kasus rekursif adalah barisan bilangan fibonacci. Barisan bilangan fibonacci adalah 1, 1, 2, 3, 5, 8, 13, 21, ... . Definisi barisan bilangan fibonacci adalah sebagai berikut. Misalkan fibonacci(i) menyatakan bilangan fibonacci yang ke-i, maka: 2 , 1,1 2,)2() 1( )( i iifibobacciifibonacci ifibonacci
Next read halaman 3