Contoh Soal Algoritma Menghitung Nilai Faktorial Bilangan N

Function Faktorial (input n : integer) à integer

{Menghasilkan Nilai n! / n faktorial, dan n tidak negatif}

Kamus :

                        {Tidak Ada}

Algoritma :

                        input(n)

                        if ( n = 0 ) then

                          return 1

                        else

                           return  ( n* Faktorial( n - 1) )

                        endif

endfunction

Bilangan Nilai n! secara rekursif

Penyelesaian :

             1.      Tentukan Parameter ukuran input : n

             2.      Operasi Dasar :

           Base case : (n = 0)

           Recursive case : ( n * Faktorial (n-1) )

           Pilih operasi dasar dari salah satu kondisi base case / recursive case ?

           Operasi dasar yang dipilih : *

           yang dilakukan n!/(n-i) kali setiap kali fungsi rekursif dipanggil

           Maka T(n) adalah T(n) = (n - 1) + 1                untuk   n > 0

             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.

            Maka :

            Untuk input  n  tertentu misal : 5, maka recursion treenya(pohon rekursifnya) selalu sama.                   Banyak komputasi / pemanggilan fungsi rekursif tetap.

            Jadi : Tidak butuh best, worst, dan average case.

            4.      Tentukan hubungan / realasi recurrence, dengan sebuah kondisi awal, untuk jumlah waktu                   operasi dasar di eksekusi / di jalankan.

Jika T(n) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n dan             T(n - 1) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n-1.

Maka :  Hubungan T(n) dan T(n - 1) dinyatakan dengan

T(0) = 0                                   untuk   n = 0 ( base case/kasus dasar )

            T(n) =  T(n – 1) + 1                 untuk   n > 0 (recursive case/kasus rekursif)

            5.      Menyelesaikan solusi relasi rekurens yang didapat di nomor 4 (t(n))

·         Untuk mengetahui kelas efisiensi waktunya kita harus menemukan persamaan langsung ( non recursive ) dari T(n).

·         Menggunakan metode backward substitution, cari pola dari :

T(n) =  T(n – 1) + 1

T(n) =  (T(n – 2) + 1) + 1  =  T(n) =  T(n – 2) + 2

T(n) =  (T(n – 3) + 1 ) + 2 =  T(n) =  T(n – 3) + 3

Dan seterusnya

·         Pola atau bentuk umumyang didapat adalah

T(n) = T(n – i) + i

·         Nilai kondisi awal T(0) disubstitution ke T(n – i) pada bentuk umum T(n).

T(n) à T(n-i) = T(0)

T(n) = T(n - i) + i

T(n) = T(0) + i

T(n) = 0 + i

T(n) = i

·         Subtitusi tersebut mensyaratkan 

T(n – i) = T(0)

   n – i  = 0

           i = n

nilai  i = n  disubtitusikan ke bentuk umum

T(n) = i

Sehingga

T(n) = i

T(n) = n

T(n) = n

Jadi

T(n) merupakan anggota kelas n

            6.      Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)),Ω(g(n)), atau Ɵ(g(n))

            Jadi : T(n) = n

            T(n) є O(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

Contoh Soal Algoritma Menghitung Hasil Kali dari dua Bilangan ( a * b )

Function  kali ( input a,b : integer) à integer

Kamus :

                        {Tidak ada}

Algoritma :

                        Input (a,b)

                        if ( b = 1 ) then

                           return a

                        else

                           return  ( a  +  Kali(a, b – 1) )

                        endif

endfunction

Perkalian Bilangan a,b secara Rekursif

Penyelesaian

            1.      Tentukan Parameter ukuran input : b

            2.      Operasi Dasar :

       Base case : (b = 1)

       Recursive case : ( a + Kali (a, b-1) )

       Pilih operasi dasar dari salah satu kondisi base case / recursive case ?

       Operasi dasar yang dipilih : =            

       yang dilakukan 1 kali setiap kali fungsi rekursif dipanggil

       Maka T(n) adalah T(1) = 1                  untuk   b = 1

           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.

           Maka :

           Untuk input  n  tertentu misal : 4, maka recursion treenya(pohon rekursifnya) selalu sama.                    Banyak komputasi / pemanggilan fungsi rekursif berbeda.

           Jadi : Butuh best, worst, dan average case.

          4.      Tentukan hubungan / realasi recurrence, dengan sebuah kondisi awal, untuk jumlah waktu                    operasi dasar di eksekusi / di jalankan.

Jika T(n) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n dan             T(n - 1) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n-1.

Maka :  Hubungan T(n) dan T(n - 1) dinyatakan dengan

T(1) = 1                                   untuk   b = 1 ( base case/kasus dasar )

            T(n) =  T(n – 1) + 1                 untuk   b > 1 (recursive case/kasus rekursif)

          5.      Menyelesaikan solusi relasi rekurens yang didapat di nomor 4 (t(n))

·         Untuk mengetahui kelas efisiensi waktunya kita harus menemukan persamaan langsung ( non recursive ) dari T(n).

·         Menggunakan metode backward substitution, cari pola dari :

T(n) =  T(n – 1) + 1

T(n) =  (T(n – 2) + 1) + 1  =  T(n) =  T(n – 2) + 2

T(n) =  (T(n – 3) + 1 ) + 2 =  T(n) =  T(n – 3) + 3

Dan seterusnya

·         Pola atau bentuk umumyang didapat adalah

T(n) = T(n – i) + i

·         Nilai kondisi awal T(1) disubstitution ke T(n – i) pada bentuk umum T(n).

T(n) à T(n-i) = T(1)

T(n) = T(n - i) + i

T(n) = T(1) + i

T(n) = 1 + i

T(n) = i + 1

·         Subtitusi tersebut mensyaratkan 

T(n – i) = T(1)

   n – i  = 1

           i = n – 1

nilai  i = n – 1 disubtitusikan ke bentuk umum

T(n) = i + 1

Sehingga

T(n) = i + 1

T(n) = n – 1 + 1

T(n) = n

Jadi

T(n) merupakan anggota kelas n

           6.      Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)),Ω(g(n)), atau Ɵ(g(n))

           Jadi : T(n) = n

          T(n) є O(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

Contoh Soal Algoritma Perhitungan Pangkat Secara Rekursif

function Pangkat ( x : integer, n : integer) à integer

// algoritma untuk menghitung nilai xⁿ secara rekursif

kamus :

            x, n : integer

Algoritma :

            //input : x  dan  n 

            if ( n = 0 ) then

               return  1

            else

               return  ß  x * Pangkat (x, n - 1)

            endif

            //output : nilai xⁿ

endfunction

Tampilan Perhitungan Pangkat Secara Rekursif

     

    Penyelesaian :

          1.     Tentukan Parameter ukuran input : n
          2.     Operasi Dasar :

                           Base case : (n = 0) 

               Recursive case : ( x * Pangkat (x, n-1) )

               Pilih operasi dasar dari salah satu kondisi base case / recursive case ?

              Operasi dasar yang dipilih : =             

              yang dilakukan 1 kali setiap kali fungsi rekursif dipanggil

              Maka T(n) adalah T(0) = 0                  untuk   n = 0

          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.

                   Maka :

                   Untuk input  n  tertentu misal : 5, maka recursion treenya(pohon rekursifnya) selalu sama.                    Banyak komputasi / pemanggilan fungsi rekursif tetap ( 5 kali ).

                   Jadi : tidak butuh best, worst, dan average case.

                4.     Tentukan hubungan / realasi recurrence, dengan sebuah kondisi awal, untuk jumlah waktu                    operasi dasar di eksekusi / di jalankan.

     Jika T(n) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n dan                    T(n - 1) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n-1.

     Maka :  Hubungan T(n) dan T(n - 1) dinyatakan dengan

     T(0) = 0                                   untuk   n = 0 ( base case/kasus dasar )

                 T(n) =  T(n – 1) + 1                 untuk   n > 0 (recursive case/kasus rekursif)

               5.     Menyelesaikan solusi relasi rekurens yang didapat di nomor 4 (t(n))

·         Untuk mengetahui kelas efisiensi waktunya kita harus menemukan persamaan langsung ( non recursive ) dari T(n).

·         Menggunakan metode backward substitution, cari pola dari :

T(n) =  T(n – 1) + 1

T(n) =  (T(n – 2) + 1) + 1  =  T(n) =  T(n – 2) + 2

T(n) =  (T(n – 3) + 1 ) + 2 =  T(n) =  T(n – 3) + 3

Dan seterusnya

·         Pola atau bentuk umumyang didapat adalah

T(n) = T(n – i) + i

·         Nilai kondisi awal T(0) disubstitution ke T(n – i) pada bentuk umum T(n).

T(n) = T(n - i) + i

T(n) = T(0) + i

T(n) = 0 + i

T(n) = i

·         Subtitusi tersebut mensyaratkan 

T(n – i) = T(0)

   n – i  = 0

           i = n

nilai  i = n  disubtitusikan ke bentuk umum

T(n) = i

Sehingga

T(n) = i

T(n) = n

Jadi

T(n) merupakan anggota kelas n

               6.     Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)),Ω(g(n)), atau Ɵ(g(n))

                 Jadi : T(n) = n

                T(n) є O(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

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