ANALISIS REKURENS / REKURSIF

ANALISIS REKURENS, seperti Looping tapi ini berbeda, dapat memanggil dirnya sendiri.

Rekursif adalah salah satu metode dalam dunia matematika dimana definisi sebuah fungsi mengandung fungsi itu sendiri.

Dalam dunia pemrograman, rekursi diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri. Contoh fungsi rekursif misalnya adalah fungsi pangkat, faktorial, dan barisan fibonacci.

Definisi Rekursif

Rekursif : metode matematika yakni definisi sebuah fungsi mengandung fungsi itu sendiri.

Rekursif : fungsi yang memanggil dirinya sendiri dan tergolong dalam dynamic programming (atau biasa disingkat dengan DP).

Rekursif: suatu kemampuan subrutin / subprogram untuk memanggil dirinya sendiri.

Dynamic programming, yang menyelesaikan suatu problem dengan mengkombinasikan solusi menjadi subproblem

Type Rekursif

• Type rekursif :

– Jika teks yang mendefinisikan type mengandung referensi terhadap diri sendiri, maka type disebut type rekursif.

– Type dibentuk dengan komponen yang merupakan type itu sendiri.

Kerangka Fungsi Rekursif

F (Param):

if (kondisi Basis) (* Basis-0 atau Basis-1 *)

then

F:= Ekspresi<berhenti>

else

(* Rekurens *)

Ekspresi( F (Param mengecil));

Kenapa Membuat Program Rekursif?

• Persoalan yang ingin diselesaikan memang

   mengandung definisi “rekursif”.

• Program yang dibuat mengolah data bertype rekursif.

• Karena programmernya ingin menulis solusi rekursif Persoalan yang tidak rekursif tidak perlu diselesaikan secara rekursif, tapi bisa diselesaikan secara rekursif. Ada banyak jalan menuju ke Semarang…...

CONTOH REKURSIF

FAKTORIAL DENGAN REKURSIF

Logika faktorial :

4! = 4 x 3 x 2 x 1             4! = 4 x 3!

3! = 3 x 2 x 1                   3! = 3 x 2!

2! = 2 x 1               -->     2! = 2 x 1!

1! = 1                               1! = 1

Syarat faktorial :

n=0 maka n!=1

n>0 maka n!=n*(n-1)!

Jadi proses rekursif akan selalu memanggil dirinya sendiri dengan variabel yang berbeda, dan terus dilakukan sampai mencapai base step. Setelah itu maka akan mendapatkan hasil dan selanjutnya hasil tersebut dikembalikan ke pemanggilnya untuk dilakukan perhitungan. Hal itu dilanjutkan sampai ke pemanggil yang pertama sehingga mendapatkan hasil sebagaimana mestinya.

PENJUMLAHAN BERURUTAN DALAM REKURSIF

PANGKAT DALAM REKURSIF

PERKALIAN DALAM REKURSIF

Menghitung perkalian dua bilangan menggunakan teknik rekursif :

CONTOH
a = 2 ; b = 4

int kali(int a, int b)

{

if(b==0) return 0;

else return a + kali(a,b-1);

}

kali(2, 4)

-> 2 + kali(2, 3)

-> 2 + (2 + kali(2, 2))

-> 2 + (2 + (2 + kali(2, 1)))

-> 2 + (2 + (2 + (2 + kali(2, 0))))

-> 2 + (2 + (2 + (2 + 0)))

-> 2 + (2 + (2 + 2)

-> 2 + (2 + 4)

-> 2 + 6

-> 8