Struktur Data - Dasar-dasar Rekursi

Beberapa bahasa pemrograman komputer memungkinkan modul atau fungsi untuk memanggil dirinya sendiri. Teknik ini dikenal sebagai rekursi. Dalam rekursi, sebuah fungsiα baik memanggil dirinya sendiri secara langsung atau memanggil suatu fungsi β yang pada gilirannya memanggil fungsi asli α. Fungsinyaα disebut fungsi rekursif.

Example - fungsi yang memanggil dirinya sendiri.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - fungsi yang memanggil fungsi lain yang pada gilirannya memanggilnya lagi.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Properti

Fungsi rekursif bisa menjadi tak terbatas seperti loop. Untuk menghindari berjalannya fungsi rekursif tanpa batas, ada dua properti yang harus dimiliki fungsi rekursif -

• Base criteria - Harus ada setidaknya satu kriteria atau kondisi dasar, sehingga, ketika kondisi ini terpenuhi, fungsi berhenti memanggil dirinya sendiri secara rekursif.

• Progressive approach - Panggilan rekursif harus berkembang sedemikian rupa sehingga setiap kali panggilan rekursif dibuat, itu mendekati kriteria dasar.

Penerapan

Banyak bahasa pemrograman mengimplementasikan rekursi melalui stacks. Umumnya, setiap kali suatu fungsi (caller) memanggil fungsi lain (callee) atau dirinya sendiri sebagai callee, fungsi pemanggil mentransfer kontrol eksekusi ke callee. Proses transfer ini mungkin juga melibatkan beberapa data untuk diteruskan dari pemanggil ke penerima.

Artinya, fungsi pemanggil harus menangguhkan eksekusinya untuk sementara dan melanjutkannya nanti saat kontrol eksekusi kembali dari fungsi callee. Di sini, fungsi pemanggil harus dimulai tepat dari titik eksekusi yang menahannya. Itu juga membutuhkan nilai data yang sama persis dengan yang sedang dikerjakannya. Untuk tujuan ini, catatan aktivasi (atau bingkai tumpukan) dibuat untuk fungsi pemanggil.

Catatan aktivasi ini menyimpan informasi tentang variabel lokal, parameter formal, alamat pengirim dan semua informasi yang diteruskan ke fungsi pemanggil.

Analisis Rekursi

Orang mungkin berdebat mengapa menggunakan rekursi, karena tugas yang sama dapat dilakukan dengan iterasi. Alasan pertama adalah, rekursi membuat program lebih mudah dibaca dan karena sistem CPU terbaru yang disempurnakan, rekursi lebih efisien daripada iterasi.

Kompleksitas Waktu

Dalam kasus iterasi, kami mengambil jumlah iterasi untuk menghitung kompleksitas waktu. Demikian juga, dalam kasus rekursi, dengan asumsi semuanya konstan, kami mencoba mencari tahu berapa kali panggilan rekursif dilakukan. Panggilan yang dilakukan ke suatu fungsi adalah Ο (1), maka (n) berapa kali panggilan rekursif dibuat membuat fungsi rekursif Ο (n).

Kompleksitas Ruang

Kompleksitas ruang dihitung sebagai jumlah ruang ekstra yang diperlukan untuk menjalankan modul. Dalam kasus iterasi, kompilator hampir tidak membutuhkan ruang ekstra. Kompilator terus memperbarui nilai variabel yang digunakan dalam iterasi. Namun dalam kasus rekursi, sistem perlu menyimpan catatan aktivasi setiap kali panggilan rekursif dilakukan. Oleh karena itu, dianggap bahwa kompleksitas ruang dari fungsi rekursif mungkin lebih tinggi daripada fungsi dengan iterasi.