Rekursif

REKURSIF

Pengertian Rekursif

Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.

            Contoh paling sederhana dari proses rekursif ini adalah proses menghitung nilai factorial dari suatu bilangan bulat positif dan mencari deret Fibbonacci dari suatu bilangan bulat.

1. Nilai factorial secara rekursif dapat ditulis sebagai

0 ! = 1

N ! = N x (N-1) !

yang secara pemrograman dapat ditulis sebagai

Faktorial(0)  = 1                                                                                 (1)

Faktorial(N) = N*Faktorial(N-1)                                                     (2)

Persamaan (2) di atas adalah contoh hubungan rekurens (recurrence relation), yang berarti bahwa nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil. Persamaan (1) tidak bersifat rekursif, disebut nilai awal atau basis. Setiap fungsi rekursif paling sedikit  mempunyai satu nilai awal, jika tidak fungsi tersebut tidak bisa dihitung secara eksplisit.

2. Bilangan Fibbonacci didefinisikan sebagai berikut

                 1    1    2    3    5    8    13    21    34    55    89   …

dari barisan tersebut dapat dilihat bahwa bilangan ke-N (N>2) dalam barisan dapat dicari dari dua bilangan sebelumnya yang terdekat dengan bilangan N, yaitu bilangan ke-(N-1) dan bilangan ke-(N-2), sehingga dapat dirumuskan sebagai

Fibbonacci(1) = 1                                                                               (1)

Fibbonacci(2) = 1                                                                               (2)

Fibbonacci(N) = Fibbonacci(N-1) + Fibbonacci(N-2)                    (3)

            Dengan persamaan (1) dan (2) adalah basis dan persamaan (3) adalah rekurensnya

Rekursif Versus Iteratif

            Dalam beberapa situasi, pemecahan secara rekursif maupun secara iteratif mempunyai keuntungan dan kekurangan yang bisa saling diperbandingkan. Adalah cukup sulit untuk menentukan mana yang paling sederhana, paling jelas, paling efisien dan paling mudah disbanding yang lain. Boleh dikatakan pemilihan cara iterative maupun rekursif merupakan kesenangan seorang programmer dan tergantung konteks permasalahan yang akan dipecahkan sesuai dengan kesanggupan yang bersangkutan.

Perhatikanlah contoh berikut :

Contoh 1.

function FACT(N : integer) ® integer

{mengirimkan bilangan factorial dengan cara rekursif}

 Deklarasi

 Deskripsi

      if (N=0) then

          return 1                {Basis}

      else

          return(N*FACT(N-1)) {Rekurens}

      endif

Contoh 2.

function FIBO(N : integer) ® integer

{mengirimkan bilangan fibbonacci dengan cara rekursif}

Deklarasi

Deskripsi

     if ((N=1) or (N=2)) then

          return 1                {Basis}

     else

          return(FIBO(N-1)+ FIBO(N-2))      {Rekurens}

     endif

Contoh 3.

function FACT(N : integer) ® integer

{mengirimkan bilangan factorial dengan cara iteratif}

Deklarasi

          x,i : integer

Deskripsi

          x ¬ 1

                        for  i = 1 to N do

                                    x ¬ i*x

                        endfor

                         return x

 Contoh 4.

function FIBO(N : integer) ® integer

{mengirimkan bilangan fibbonacci dengan cara iteratif}

Deklarasi

          Fibbonacci, Akhir, Bantu, i : integer

Deskripsi

If N=0 then

              return 0

          else

            i¬1

  Fibbonacci ¬1

  Akhir ¬0

  while (i¹N)do

              Bantu ¬ Fibbonacci

              i ¬ i + 1

              Fibbonacci ¬ Fibbonacci + Akhir

              Akhir ¬ Bantu

   Endwhile

        return Fibbonacci

      endif