Algoritma - Rekursif

Pada bahasa pemrograman terdapat fungsi yang memanggil dirinya sendiri atau dengan kata lain penggunaan fungsinya menjadi abstraksi untuk kode-kode yang digunakan berulang kali. Rekursif, ya inilah sebuah fungsi yang memanggil dirinya sendiri. Konsep pada fungsi ini dapat digunakan ketika merumuskan solusi sederhana yang terjadi di sebuah permasalahan yang sulit namun bisa diselesaikan secara iterative. Ciri permasalah yang dapat diselesaikan dengan rekursif adalah masalah tersebut direduksi menjadi satu atau lebih masalah-masalah serupa yang lebih kecil. Maka dalam suatu algoritma rekursif bisa digunakan dengan satu atau lebih kasus yang pemecahan masalahnya dilakukan dengan menyelesaikan masalah serupa secara lebih sederhana atau istilahnya recursive call.

Misalnya:

x*pangkat (x, n-1)
35 = 3*34 = 3*81 =243
  34 = 3*33 = 3*27 = 81
    33 = 3*32 = 3*9 = 27
      32 = 3*31 = 3*3 = 9
        31 = 3*30 = 3*1= 3
          30 = 1

Algoritma :

//input : x  dan  n  
int faktorial (int n){
if ( n == 0 )
  return 1;
return n * faktorial(n-1);
}

Kelemahan algoritma rekursif dapat memakan memori yang lebih besar, sebab melakukan fungsi yang bagian dirinya dipanggil secara berulang-ulang, sehingga kadang mengorbankan efisiensi dan kecepatan. Masalah lainnya ketika rekursif tidak bisa “berhenti” maka memori akan terpakai habis dan program bisa hang atau sulit terbaca.

Karena fungsi rekursif bisa tak terbatas dan tidak bisa “berhenti” seperti loop maka untuk menghindari berjalannya fungsi rekursif, ada dua properti yang harus dimiliki fungsi rekursif:

Kriteria dasar (Base criteria) - Setidaknya harus ada satu kriteria atau kondisi dasar, yang ketika kondisi ini terpenuhi, fungsi berhenti memanggil dirinya secara rekursif.

Pendekatan Progresif (Progressive approach) - Panggilan rekursif harus maju sedemikian rupa sehingga setiap kali panggilan rekursif dibuat lebih dekat dengan kriteria dasar.

Seperti contoh divatas, Salah satu informasi yang didesain adalah kapan algoritma berhenti melakukan rekursif, yaitu n == 0 dan juga terdapat Informasi lain yaitu berkurangnya jumlah data pada setiap pemanggilan

Dari kelemahan rekursif ini, kadang programmer berpikir mengapa mesti menggunakan rekursi, sedangkan fungsi yang sama bisa dilakukan dengan iterasi, namun hal mendasar dari atau kelebihan dari rekursi ini adalah kita bisa membuat program lebih mudah dibaca apalagi sistem CPU terbaru yang disempurnakan yang membuat rekursif lebih efisien daripada iterasi. Apalagi Kode program pada iterasi lebih panjang sehingga beberapa kasus solusi iteratif lebih sulit diterapkan.

Dan dalam beberapa kasus, permasalahan iterasi yang mempunyai kompilator sangat membutuhkan ruang tambahan, terdapat masalah pada Space complexity atau Kompleksitas ruang, dimana diperlukan sebuah modul untuk dieksekusi. Kompilator ini terus memperbarui nilai variabel yang digunakan dalam iterasi. Sebaliknya sistem hanya perlu menyimpan catatan aktivasi setiap kali panggilan pada rekursif dibuat. Oleh karena itu, dianggap bahwa kompleksitas ruang fungsi rekursif bisa lebih tinggi daripada fungsi dengan iterasi.