Analisa Efisiensi Algoritma Rekursif

Rekursif

Rekursif berarti suatu proses yang memanggil dirinya sendiri. Dalam rekursif sebenarnya terkandung pengertian prosedur atau fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi. Rekursif merupakan teknik pemrograman yang penting, dan beberapa bahasa pemrograman modern mendukung keberadaan proses rekursif ini.

Langkah-langkah untuk mendefinisikan fungsi dengan domain bilangan cacah:

        1.      Langkah basis : Definisikan nilai fungsi pada saat nol.

        2.      Langkah rekursif : Berikan aturan untuk mencari nilai fungs iuntuk setiap bilangan bulat    

              berdasarkan nilai fungsi pada bilangan bulat yang lebih kecil.

Bentuk rekursif :

        1.      Suatu subrutin/fungsi/ prosedur yang memanggil dirinya sendiri.

        2.      Bentuk dimana pemanggilan subrutin terdapat dalam body subrutin

        3.      Dengan rekursi, program akan lebih mudah dilihat

Bentuk rekursi bertujuan untuk

        1.      menyederhanakan penulisan program 

        2.      menggantikan bentuk iterasi

Syarat bentuk rekursif

         1.      Ada kondisi terminal (basis) 

         2.      Ada subroutine pemanggilan (call)  yang melibatkan parameter yang nilainya menuju kondisi 

               terminal (recurrence)

Kelebihan perulangan rekursif

         1.      Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan 

               perulangan dalam skala yang besar

         2.      Dapat melakukan perulangan dengan batasan fungsi

Kekurangan perulangan rekursif

         1.      Tidak bisa melakukan nested loop atau looping bersarang.

         2.      Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja.

         3.      Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan 

               parameter formal akan ditempatkan ke stack dan ada kalaya akan menyebabkan stack tak 

               cukup lagi (Stack Overum).

         4.      Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan 

               pemanggilan data yang ditumpuk.

Permasalahan yang dapat diselesaikan oleh fungsi rekursif memiliki sifat

• ·           Memiliki kasus sederhana yang dapat langsung diselesaikan (base case). Contoh 0! = 1.
• ·         Kasus yang kompleks dapat diuraikan menjadi kasus yang identik dengan ukuran yang lebih    kecil (recursive cases). Contoh: n! = n * (n-1)!
• ·        Dengan menerapkan karakteristik 2 berulang-ulang, recursive cases akan mendekati dan sampai pada base case. Contoh: n! à (n-1)! à (n-2)! à . . . 1!, 0!.

Format Fungsi Rekursif :

if this base case

solve it

else

redefine the problem using recursion case

• ·         Cabang if berisi base case, sedangkan bagian elsenya berisi recursive case
• ·  Agar rekursi dapat berhenti input recursive cases harus mendekati base case di setiap pemanggilan fungsi rekursif

Langkah Analisa Efisiensi Algoritma Rekursif

1.      Tentukan Parameter ukuran input.
2.   Tentukan operasi dasar dari algoritma (loop terdalam).
3.     Perhatikan apakah butuh best, worst, dan average case ? Jika jumlah eksekusi suatu operasi    dasar bervariasi(berbeda) untuk berbagai input berukuran sama, maka dibutuhkan perhitungan  best, worst, dan average case.
4.  Tentukan hubungan / realasi recurrence, dengan sebuah kondisi awal, untuk jumlah waktu  operasi dasar di eksekusi / di jalankan.
5.  Menyelesaikan solusi relasi rekurens yang didapat di nomor 4 (t(n)).
6.  Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)),Ω(g(n)), atau Ɵ(g(n)).

Sumber :

• Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi). Bandung ; INFORMATIKA.
• https://zaharaahyesa.wordpress.com/2014/04/10/algoritma-rekursif/

• https://bertzzie.com/knowledge/analisis-algoritma/Rekursif.html