11 rekursi

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 1/20

REKURSIOleh: M. Ade Erik (19870911 201001 1 006)

Doc Versi. 11.00/Pas/OSN/TIK/2010

SMA Negeri 1 Tegal

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 2/20

Pembahasan:

Faktorial

Perkalian

Pencarian Biner 

Quick Short

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 3/20

Rekursi

Rekursi Mer upakan teknik pemanggilan r utin oleh dirinya

sendiri.

Rekursi juga digunakan untuk menyedarhanakan

algoritma yang ada sehingga penulisan program lebihefesien.

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 4/20

Contoh Efesiensi

f unction

faktorial(x:integer):integer;

var i, hasil:integer;

begin hasil:=1;

for i:=x downto 1 do begin

hasil:=hasil*i;

end;

faktorial:=hasil;

End;

f unction

faktorial2(x:integer):integ

er;

begin

if (x=0) then faktorial2:=1

else

faktorial2:=x*faktorial2(x-

1);

end;

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 5/20

Rekursi Faktorial

Faktorial: contoh: 5! = 5x4x3x2x1 = 120 atau 5x4! = 120

Maka bentuk rekursinya:

f unction faktorial(x:integer):integer;

begin

if (x=0) then faktorial:=1

else

faktorial:=x*faktorial(x-1);

end;

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 6/20

Penjelasan

Faktorial(5)=5*faktorial(4)

Faktorial(4)=4*faktorial(3)

Faktorial(3)=3*faktorial(2)

Faktorial(2)=2*faktorial(1)

Faktorial(1)=1*faktorial(0)

faktorial(0)=1

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 7/20

Rekursi Per pangkatan

Per pangkatan: contoh: x^y= x*x^(y-1) = 3*3^4 = 3^5

Maka bentuk rekursinya:

f unction per pangkatan(x,y:integer):integer;

begin

if (y=0) then per pangkatan:=1

else

per pangkatan:=x*per pangkatan(x,y-1);

end;

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 8/20

Penjelasan

pangkat(5,3)=5*pangkat(5,2)

pangkat(5,2)=5*pangkat(5,1)

pangkat(5,1)=5*pangkat(5,0)

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 9/20

Rekursi Fibonacci

bilangan Fibonacci adalah barisan yang didefinisikan

secara rekursif sebagai berikut:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,

987, 1597, 2584, 4181, 6765, 10946..

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 10/20

Rekursi Fibonacci

f unction fibonacci(x:integer):integer;

begin

if (x=0) then fibonacci:=0

else

if (x=1) then fibonacci:=1

else

fibonacci:=fibonacci(x-1)+fibonacci(x-2);

end;

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 11/20

Bubble Sort

Teknik ini menyusun data yang diinginkan secara

ber ur utan dengan membandingkan elemen data yang

ada.

Syntact procedure bsort(x:integer);

var i,j,t:integer;

begin

for i:=1 to x-1 do begin for j:=i+1 to x do begin

if data[i]>data[j] then begin swap(data[i],data[j]); end;

end; end;end;

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 12/20

Ilustrasi Bouble Sort

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 13/20

Contoh

uses wincrt;

type larik=array [1..7] of integer;

var data:larik;n,k:integer;

procedure swap(var c,d:integer);

var t:integer; begin

t:=c; c:=d; d:=t;

end;

procedure bsort(x:integer);

var i,j,t:integer;

begin

for i:=1 to x-1 do begin

for j:=i+1 to x do begin

if data[i]>data[j] then begin

swap(data[i],data[j]); end;

end; end; end;

begin

n:=7;

for k:=1 to n do

begin

write('data ke ',k,'= ');readln(data[k]);

end;

bsort(n);

writeln('==bouble sort==');

for k:=1 to n do

begin

write(data[k],' '); end;

end.

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 14/20

Quick Sort

Membandingkan suatu elemen (disebut pivot) dengan

elemen yang lain dan menyusunnya sedemikian r upa

sehingga elemen- elemen lain yang lebih kecil daripada

pivot tersebut terletak di sebelah kirinya dan elemen-

elemen lain yang lebih besar daripada pivot tersebut

terletak di sebelah kanannya. Sehingga dengan demikian

telah terbntuk dua sublist, yang terletak di sebelah kiri dan

kanan dari pivot. Lalu pada sublist kiri dan sublist kanan

kita anggap sebuah list bar u dan kita kerjakan prosesyang sama seperti sebelumnya. Demikian seter usnya

sampai tidak terdapat sublist lagi. Sehingga didalamnya

telah terjadi proses Rekursif.

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 15/20

IlustrasiQuick Sort

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 16/20

 AlgoritmaQuicksort

procedure qsort(a,b:integer);

Var pivot: integer; left, right: integer;

begin

if (b > a) then begin pivot := data[(a + b) div 2]; left := a; right := b;

while (left <= right) do begin

while (data[left] < pivot) do left := left + 1;

while (data[right] > pivot) do right := right - 1;

if (left <= right) then begin swap(data[left],data[right]);

left := left + 1;right := right - 1;

end;end;qsort(a, right);qsort(left, b);end;end;

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 17/20

Contoh

uses wincrt;

type larik=array [1..7] of integer;

var data:larik;n,k:integer;

procedure swap(var c,d:integer);

var t:integer; begin

t:=c; c:=d; d:=t;

end;

procedure qsort(a,b:integer);

Var pivot: integer; left, right: integer;

begin

if (b > a) then begin

pivot := data[(a + b) div 2]; left := a; right := b;

while (left <= right) do begin

while (data[left] < pivot) do left := left + 1;

while (data[right] > pivot) do right := right - 1;

if (left <= right) then begin

swap(data[left],data[right]);

left := left + 1;right := right - 1;

end; end; qsort(a, right); qsort(left, b);

end;end;

begin

n:=7;

for k:=1 to n do

begin

write('data ke ',k,'= ');readln(data[k]);

end;

qsort(1,n);

writeln('==quicksort==');

for k:=1 to n do

begin

write(data[k],' ');

end;

end.

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 18/20

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 19/20

8/8/2019 11 Rekursi

http://slidepdf.com/reader/full/11-rekursi 20/20

Contoh

uses wincrt;

type larik=array [1..7] of integer;

var data:larik;n,k:integer;

f unction bsearch(cari,n:integer):integer;

var atas,tengah,bawah:integer;

ketemu :boolean; Begin

atas:=n;bawah:=1;ketemu:=false;

while not(ketemu) do begin

tengah:=(atas+bawah) div 2;

If data[tengah]=cari then begin

ketemu:=tr ue;

bsearch:=tengah;

end

else if cari<data[tengah] then

atas:=tengah-1

else bawah:= tengah+1;

if (bawah>atas) then begin

ketemu:=tr ue;

bsearch:=0; end; end; end;

Begin n:=7;

for k:=1 to n do begin

write('data ke ',k,'= ');readln(data[k]);

end; qsort(1,n);

writeln('==quick sort==');

for k:=1 to n do begin

write(data[k],' ');

writeln; end;

write('cari data=');readln(k);

write('hasil=',bsearch(k,n)); end.