Algoritma dimana suatu fungsi atau prosedur memanggil dirinya sendiri disebut?

PROSEDUR dan FUNGSI REKURSIF

Link/anchor:

PROSEDUR dan FUNGSI REKURSIF
Prosedur dan fungsi merupakan sub program yang sangat bermanfaat dalam pemrograman, terutama untuk program atau proyek yang besar. Manfaat penggunaan sub program antara lain adalah :

Prosedur dan fungsi merupakan sub program yang sangat bermanfaat dalam pemrograman, terutama untuk program atau proyek yang besar. Manfaat penggunaan sub program antara lain adalah :

meningkatkan readibility, yaitu mempermudah pembacaan program
meningkatkan modularity, yaitu memecah sesuatu yang besar menjadi modul-modul atau bagian-bagian yang lebih kecil sesuai dengan fungsinya, sehingga mempermudah pengecekan, testing dan lokalisasi kesalahan.
meningkatkan reusability, yaitu suatu sub program dapat dipakai berulang kali dengan hanya memanggil sub program tersebut tanpa menuliskan perintah-perintah yang semestinya diulang-ulang.

Sub Program Rekursif adalah sub program yang memanggil dirinya sendiri selama kondisi pemanggilan dipenuhi.

adalah Dengan melihat sifat sub program rekursif di atas maka sub program rekursif harus memiliki :

kondisi yang menyebabkan pemanggilan dirinya berhenti (disebut kondisi khusus atau special condition)
pemanggilan diri sub program (yaitu bila kondisi khusus tidak dipenuhi)

Secara umum bentuk dari sub program rekursif memiliki statemen kondisional :

if kondisi khusus tak dipenuhi
then panggil diri-sendiri dengan parameter yang sesuai
else lakukan instruksi yang akan dieksekusi bila kondisi khusus dipenuhi

Sub program rekursif umumnya dipakai untuk permasalahan yang memiliki langkah penyelesaian yang terpola atau langkah-langkah yang teratur. Bila kita memiliki suatu permasalahan dan kita mengetahui algoritma penyelesaiannya, kadang-kadang sub program rekursif menjadi pilihan kita bila memang memungkinkan untuk dipergunakan. Secara algoritmis (dari segi algoritma, yaitu bila kita mempertimbangkan penggunaan memori, waktu eksekusi sub program) sub program rekursif sering bersifat tidak efisien .
Dengan demikian sub program rekursif umumnya memiliki efisiensi dalam penulisan perintah, tetapi kadang tidak efisien secara algoritmis. Meskipun demikian banyak pula permasalahan-permasalahan yang lebih sesuai diselesaikan dengan cara rekursif (misalnya dalam pencarian / searching, yang akan dibahas pada pertemuan-pertemuan yang akan datang).

Contoh sub program rekursif dalam bahasa Pascal.

Contoh sederhana

PROCEDURE TULIS_1(banyak : integer;kata : string); begin if banyak > 1 then TULIS_1(banyak-1,kata); writeln(kata, banyak:5); end;

OUTPUT (misal dipanggil dengan TULIS_1(5,"Cetakan ke "))

Cetakan ke 5

Bandingkan prosedur dan outputnya di atas dengan prosedur di bawah ini! PROCEDURE TULIS_2(banyak : integer;kata : string); begin writeln(kata, banyak:5); if banyak > 1 then TULIS_1(banyak-1,kata);

end;

OUTPUT (misal dipanggil dengan TULIS_2(5,"Cetakan ke ")) Cetakan ke 5 Cetakan ke 4 Cetakan ke 3 Cetakan ke 2

Cetakan ke 1

Mengapa hasilnya jauh berbeda?

Contoh terapan

Secara matematis, perkalian dua bilangan bulat positif a dengan b (ditulis ab atau a x b) pada hakekatnya merupakan penjumlahan dari a sebanyak b suku, yaitu a + a + a + …. + a sebanyak b suku. Misalnya 2 x 3 dapat diartikan sebagai 2 + 2 + 2 = 6 , yaitu penjumlahan 2 sebanyak 3 suku Dengan mengingat bahwa suatu bilangan bila dikalikan dengan angka 1 (satu) akan menghasilkan bilangan itu sendiri, maka permasalahan perkalian dengan menyatakannya dalam bentuk penjumlahan di atas dapat diselesaikan dengan komputer secara mudah.

Kembali ke atas

Dengan prosedur

end;

Dengan fungsi

Function KALI_BIASA_F(a,b:integer):longint; var hasil : longint; i: integer; begin hasil := 0; for i:= 1 to b do hasil := hasil + a; KALI_BIASA_F := hasil;

Rekursif

Rekursif Proses yang memanggil dirinya sendiri. Merupakan suatu fungsi atau prosedur Terdapat suatu kondisi untuk berhenti.

Faktorial Konsep Faktorial n! = n(n-1)(n-2) 1 Dapat diselesaikan dengan Cara Biasa Rekursif

Faktorial

Faktorial : Cara Biasa int Faktorial(int n) { if (n<0) return -1 ; else if (n>1) { S = 1 ; for(i=2 ;i<=n;i++) S = S * n ; return S ; else return 1 ;

Faktorial dengan Rekursif int Faktorial(int n) { if (n<0) return -1; else if (n>1) return (n*faktorial(n-1)) else return 1 ;

Deret Fibonacci Leonardo Fibonacci berasal dari Italia 1170-1250 Deret Fibonacci f 1, f 2, didefinisikan secara rekursif sebagai berikut : f 1 = 1 f 2 = 2 f n = f n-1 + f n-2 for n > 3 Deret: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,

Deret Fibonacci

1-10 Tower Hanoi Tower Hanoi adalah permainan puzzle dengan tiga tiang dan sejumlah disk/cakram yang tersusun pada tiang. Disk memiliki ukuran yang bervariasi. Disk-disk tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, disk terkecil diletakkan teratas, sehingga membentuk kerucut. Tujuan adalah untuk memasukkan semua disk dari tiang awal ke tiang tujuan dengan menggunakan tiang bantuan dengan aturan : Hanya satu disk dapat dipindahkan pada suatu waktu Sebuah disk tidak dapat ditempatkan di atas disk yang lebih kecil

1-11 The Towers of Hanoi puzzle

1-12 A solution to the three-disk Towers of Hanoi puzzle

Towers of Hanoi Untuk memindahkan N disk dari tiang asal ke tiang tujuan : Pindahkan N-1 disk yang paling atas dari tiang asal ke tiang bantuan. Pindahkan 1 disk terbesar dari tiang asal ke tiang tujuan Pindahkan N-2 disk dari tiang bantuan ke tiang tujuan 1-13

Towers of Hanoi Jumlah perpindahkan disk bertambah secara exponential dengan bertambahnya jumlah disk Solusi secara rekursif lebih sederhana dibandingkan dengan solusi iteratif 1-14

UML description of the SolveTowers and TowersofHanoi classes 1-15

The Solve Towers class /** * SolveTowers demonstrates recursion. * * @author Dr. Lewis * @author Dr. Chase * @version 1.0, 8/18/08 */ public class SolveTowers { /** * Creates a TowersOfHanoi puzzle and solves it. */ public static void main (String[] args) { TowersOfHanoi towers = new TowersOfHanoi (4); towers.solve(); 1-16

The Towers of Hanoi class /** * TowersOfHanoi represents the classic Towers of Hanoi puzzle. * * @author Dr. Lewis * @author Dr. Chase * @version 1.0, 8/18/08 */ public class TowersOfHanoi { private int totaldisks; /** * Sets up the puzzle with the specified number of disks. * * @param disks the number of disks to start the towers puzzle with */ public TowersOfHanoi (int disks) { totaldisks = disks; 1-17

The Towers of Hanoi class (continued) /** * Performs the initial call to movetower to solve the puzzle. * Moves the disks from tower 1 to tower 3 using tower 2. */ public void solve () { movetower (totaldisks, 1, 3, 2); /** * Moves the specified number of disks from one tower to another * by moving a subtower of n-1 disks out of the way, moving one * disk, then moving the subtower back. Base case of 1 disk. * * @param numdisks the number of disks to move * @param start the starting tower * @param end the ending tower * @param temp the temporary tower */ 1-18

The Towers of Hanoi class (continued) private void movetower (int numdisks, int start, int end, int temp) { if (numdisks == 1) moveonedisk (start, end); else { movetower (numdisks-1, start, temp, end); moveonedisk (start, end); movetower (numdisks-1, temp, end, start); 1-19 /** * Prints instructions to move one disk from the specified start * tower to the specified end tower. * * @param start the starting tower * @param end the ending tower */ private void moveonedisk (int start, int end) { System.out.println ("Move one disk from " + start + " to " + end);

Multibase Representations Decimal is only one representation for numbers. Other bases include 2 (binary), 8 (octal), and 16 (hexadecimal). Hexadecimal uses the digits 0-9 and a=10, b=11, c=12, d=13, e=14, f=16. 95 = 1011111 2 // 95 = 1(2 6 )+0(2 5 )+0(2 4 )+0(2 3 )+1(2 2 )+1(2 1 )+1(2 0 ) = 1(64)+0(32)+1(16)+1(8)+1(4)+1(2)+1 95 = 340 5 // 95 = 3(52) + 4(51) + 0(5 0 ) = 3(25) + 4(5) + 0 95 = 137 8 // 95 = 1(82) + 3(81) + 7(8 0 ) = 1(64) + 3(8) + 7 748 = 2ec 16 // 748 = 2(16 2 ) + 14(16 1 ) + 12(16 0 ) = 2(256) + 14(16) + 12 = 512 + 224 + 12

Multibase Representations (continued) An integer n > 0 can be represented in different bases using repeated division. Generate the digits of n from right to left using operators '%' and '/'. The remainder is the next digit and the quotient identifies the remaining digits.

Multibase Representations (continued)

Multibase Representations (continued) Convert n to base b by converting the smaller number n/b to base b (recursive step) and adding the digit n%b.

Multibase Representations (continued) // returns string representation // of n as a base b number public static String basestring(int n, int b) { String str = "", digitchar = "0123456789abcdef"; // if n is 0, return empty string if (n == 0) return ""; else { // get string for digits in n/b str = basestring(n/b, b); // recursive step // return str with next digit appended return str + digitchar.charat(n % b);

Multibase Representations (concluded)

Rekursif Tail Jika hasil akhir yang akan dieksekusi berada dalam tubuh fungsi Tidak memiliki aktivitas selama fase balik.

What is Tail Recursion? Metode rekursif Tail recursive Nontail recursive Method tail recursive memiliki pemanggilan rekursif di akhir method. Recursive methods yang bukan tail recursive disebut non-tail recursive

Is Factorial Tail Recursive? Apakah method faktorial adalah tail recursive? int fact(int x){ if (x==0) else return 1; return x*fact(x-1); Bukan tail recursive karena pada saat kembali dari recursive call x*fact(x- 1), masih terdapat operasi perkalian.

Another Example Apakah method tail() adalah tail recursive? void tail(int i) { if (i>0) { system.out.print(i+"") tail(i-1) Method tail() merupakan tail recursive

Third Example Apakah method prog() adalah tail recursive? void non prog(int i) { if (i>0) { prog(i-1); System.out.print(i+""); prog(i-1); Tidak, karena dibaris awal terdapat recursive call Pada tail recursive, recursive call menjadi statement akhir, dan tidak ada recursive call diatasnya.

Advantage of Tail Recursive Method Method dengan Tail Recursive, mudah dirubah menjadi iteratif void tail(int i){ if (i>0) { system.out.println(i+""); tail(i-1) void iterative(int i){ for (;i>0;i--) System.out.println(i+""); Smart compilers can detect tail recursion and convert it to iterative to optimize code Used to implement loops in languages that do not support loop structures explicilty (e.g. prolog)

Converting Non-tail to Tail Recursive Method non-tail recursive dapat diubah menjadi tail-recursive method dengan menambahkan parameter tambahan untuk menampung hasil. method fact(int n) fact_aux(int n, int result) Teknik yang digunakan biasanya membuat fungsi tambahan (method fact(int n)) yang memanggil method tail recursive. int fact_aux(int n, int result) { if (n == 1) return result; return fact_aux(n - 1, n * result) int fact(n) { return fact_aux(n, 1);

Rekursif Tail : Faktorial() F(4,1) = F(3,4) F(3,4) = F(2,12) F(2,12) = F(1,24) F(1,24) = 24 Fase awal Kondisi Terminal 24 Fase Balik Rekursif Lengkap

Converting Non-tail to Tail Recursive Method tail-recursive Fibonacci diimplementasikan menggunakan dua parameter bantuan untuk menampung hasil. int fib_aux ( int n, int next, int result) { auxiliary parameters! if (n == 0) return result; return fib_aux(n - 1, next + result, next); To calculate fib(n), call fib_aux(n,1,0)