Pilihan Rekursif
•Fungsi rekursif sangat penting dalam pemrograman terutama untuk menyederhanakan penulisan program yang kompleks. Namun fungsi rekursi juga membuat penalaran instruksi menjadi sangat sulit terutama dalam membuktikan kebenarannya.
Prosedur Rekursi
• def A(x,y) =
• select x=0: donothing
• x>0: y(); A(x-1,y)
• endselect
•Enddef
•Dalam program ini prosedur A(x,y) akan memanggil dirinya sendiri tergantung pada jumlah x yang disuplai oleh program pemanggil.
•Repetisi dalam program ini terjadi bukan karena adanya instruksi repetisi tetapi oleh pemanggilan kembali prosedur yang sama. Untuk menghindari program ini terkunci dalam looping yang tak habis-habinya maka perlu disediakan opsi untuk keluar yaitu bila x = 0.
Penalaran Dengan Rekursi
•Hal yang paling penting dalam penggunaan prosedur rekursi adalah mengetahui dengan benar bahwa suatu rekursif akan menghasilkan apa yang diinginkan dan bahwa prosedur rekursi itu tidak terjebak dalam looping terus menerus.
•Sebagai contoh untuk prosedur dalam Program di atas, bila kita memanggil prosedur ini A(4,y), maka prosedur ini akan keluar bila telah mencapai A(0,y). Namun pembuktian tidak bisa dimulai dari A(4,y) tetapi dari A(0,y) sbb:
•Bila dipanggil A(0,y)
• A(0,y)= select 0:donothing
• 0>0: A(0-1,y)
• endselect
• sehingga hasilnya adalah
• A(0,y) = donothing atau langsung selesai
•Bila dipanggil A(1,y)
• A(1,y)= select
0:donothing
1>0: y(); A(1-1,y)
endselect
• sehingga hasilnya adalah
• A(1,y) = y(); A(0,y )
• = y();
•Bila dipanggil A(2,y)
• A(2,y)= select 0:donothing
• 2>0: y(); A(2-1,y)
• endselect
• sehingga hasilnya adalah
•
• A(2,y)= y(); A(1,y )
• = y(); y();A(0,y)
• = y(); y().
•Bila dipanggil A(3,y)
• A(3,y)= select 0:donothing
• 3>0: y(); A(3-1,y)
• endselect
• sehingga hasilnya adalah
• A(3,y)= y(); A(2,y )
• = y();y(); A(1,y )
• = y();y(); y();A(0,y)
• = y(); y(); y().
•Bila dipanggil A(4,y)
• A(4,y)= select 0:donothing
• 4>0: y(); A(4-1,y)
• endselect
•
•sehingga hasilnya adalah
• A(4,y)= y();A(3,y)
• = y();y(); A(2,y )
• = y();y();y(); A(1,y )
• = y();y(); y();A(0,y)
• = y(); y(); y();y().
Mencari Formula Jumlah Rekurs
i•Untuk mengetahui dengan pasti jumlah rekursi yang terjadi dapat dilakukan dengan mencari formula perhitungannya.
•Formula itu dipakai untuk menghitung dengan tepat cacah rekursif yang terjadi.
• def A(p,q) =
• select p=0: donothing
• p>0: q();A(p-1,q);A(p-1,q)
• endselect;
• enddef;
• Ingin dicari suatu formula yang dengan tepat mengekspresikan jumlah eksekusi n() sebagai akibat pemanggilan A(m,n).
•Misalkan kita sebut formula tersebut adalah hitung(k), maka
•Bila dipanggil A(0,n)
• A(0,y)= donothing
•sehingga hitung(0) =0;
• •Bila dipanggil A(1,n)
• A(1,n)= n(); A(1-1,n);A(1-1,n)
• = n(); A(0,n);A(0,n)
• = n()
•sehingga hitung(1) =1;
•Bila dipanggil A(2,n)
• A(2,n)= n(); A(2-1,n);A(2-1,n)
• = n(); A(1,n);A(1,n)
• = n();n();n()
•sehingga hitung(2) =3;
•
•Bila dipanggil A(3,n)
• A(3,n)= n(); A(3-1,n);A(3-1,n)
• = n(); A(2,n);A(2,n)
•sehingga
• hitung(3) =1+hitung(2)+hitung(2)
• = 1+3+3
• =7
•Bila dipanggil A(4,n)
• A(4,n)= n(); A(4-1,n);A(4-1,n)
• = n(); A(3,n);A(3,n)
• sehingga
• hitung(4) =1+hitung(3)+hitung(3)
• = 1+7+7
• =15
•Dengan induktif dapat disimpulkan bahwa formula untuk menghitung jumlah eksekusi prosedur n() adalah hitung(K)= 2K - 1 eksekusi.
•def fibonacci (x) =
• select x=0: 0
• x=1: 1
x> 1: fibonacci (x-1)+fibonacci (x-2)
• endselect;
• enddef;
•Bila dipanggil: Fibonacci(5)??
Factorial (Dalam Pascal)
•N!= n(n-1)x(n-2)…
•Factorial (n ) = n * n-1 * n-2 * ... *
•Function Factorial(n : Integer) : Integer;
Var Result : Integer;
Begin If n = 1 then Factorial := 1
Else Factorial := n*Factorial(n-1);
End;
Segitiga Pascal
Tidak ada komentar:
Posting Komentar