Catatan Kuliah
STRUKTUR DATA
BAB III REKURSIF Rekursif adalah proses suatu program (fungsi / prosedur) yang memanggil dirinya sendiri. Harus diperhatikan kondisi akhir dari proses rekursif agar tidak terjadi proses yang tidak berujung. Rekursif akan mendefinisikan objek dalam bentuk kasus yang paling sederhana dari kasus tersebut.
Narwen, M.Si / Jurusan Matematika FMIPA Unand
1
Catatan Kuliah
STRUKTUR DATA
Contoh. 1. Fungsi Faktorial n factorial ditulis ‘ n ! ‘ didefinisikan sebagai perkalian semua bilangan bulat antara n dan 1. Jadi n! = n * (n–1) * (n–2) * … * 2 * 1 atau ⎧1, n = 0 n!= ⎨ ⎩ n * ( n − 1) * ... * 1 , n > 0
Kalau penulisan dirubah menjadi, ⎧1 , n = 0 n != ⎨ ⎩ n * ( n − 1)! , n > 0 Narwen, M.Si / Jurusan Matematika FMIPA Unand
2
Catatan Kuliah
STRUKTUR DATA
Maka bentuk ini diselesaikan dengan cara rekursif yaitu dengan tahapan sebagai berikut : (1) n!=n*(n–1)!
(2) (3)
(n–1)!=(n – 1)*(n–2)! (n–2)!=(n–2)*(n–3)! -------------------------------------------------(n-1) 1!=1*0! (n) 0!=1 Setelah nilai langkah ke (n) di dapat, maka dilakukan operasi penyulihan mundur yang dimulai dari langkah ke (n–1) sampai dengan langkah ke (1). Setelah pada langkah ke (1) diperoleh nilai n!. Narwen, M.Si / Jurusan Matematika FMIPA Unand
3
Catatan Kuliah
STRUKTUR DATA
Dalam bentuk fungsi rekursif, maka fungsi faktorial dapat ditulis sebagai berikut: Function fakt(n : nonneg) : nonneg; begin if n = 0 then fakt := 1 else fakt := n * fakt(n-1); End;
Latihan Buat fungsi faktorial sebagai fungsi yang iteratif.
Narwen, M.Si / Jurusan Matematika FMIPA Unand
4
Catatan Kuliah
STRUKTUR DATA
2. Perkalian Bilangan Asli Perkalian bilangan bulat positif a dengan b ‘ditulis a * b’ didefenisikan sebagai penjumlahan dari a sebanyak b kali (defenisi iterative). Secara rekursif : ⎧a , b = 1 a*b = ⎨ ⎩a * (b − 1) + a ,
b>1
atau, ⎧ b, a = 1 a*b = ⎨ ⎩b * (a − 1) + b, a > 1
Maka bentuk ini diselesaikan dengan cara rekursif yaitu dengan tahapan sebagai berikut : Narwen, M.Si / Jurusan Matematika FMIPA Unand
5
Catatan Kuliah
STRUKTUR DATA
(1) a*b = a+a*(b–1) (2) a*(b–1)=a+a*(b–2) (3) a*(b-2)=a+a*(b–3) ------------------------------------------(b–2) a*3=a+a*2 (b–1) a*2=a+a*1 (b) a*1=a Setelah nilai langkah ke (b) di dapat, maka dilakukan operasi penyulihan mundur yang dimulai dari langkah ke (b–1) sampai dengan langkah ke (1). Setelah pada langkah ke (1) diperoleh nilai a*b. Narwen, M.Si / Jurusan Matematika FMIPA Unand
6
Catatan Kuliah
STRUKTUR DATA
Dalam bentuk fungsi rekursif, maka fungsi perkalian bilangan bulat dapat ditulis sebagai berikut: Function kali(a,b : nonneg) : nonneg; begin if b = 1 then kali := a else kali := a + kali(a,b-1); End;
Latihan Buat fungsi perkalian bilangan bulat sebagai fungsi yang iteratif.
Narwen, M.Si / Jurusan Matematika FMIPA Unand
7
Catatan Kuliah
STRUKTUR DATA
3. Barisan Fibonacci Barisan Fibonacci adalah barisan bilangan bulat berbentuk 0, 1, 1, 2, 3, 5, 8, 13, 21, … atau elemen dari barisan ini adalah jumlah dari dua elemen terdahulu untuk elemen ke 3, 4 dan seterusnya. Secara rekursi didefenisikan sebagai,
n = 0, 1 ⎧ n, fib( n) = ⎨ ⎩ fib( n − 2) + fib( n − 1) , n ≥ 2
Dalam bentuk fungsi rekursif, maka fungsi barisan fibonacci dapat ditulis sebagai berikut: Narwen, M.Si / Jurusan Matematika FMIPA Unand
8
Catatan Kuliah
STRUKTUR DATA
Function fib (n : nonegInt ) : nonegInt ; Var x, y : nonegInt ; Begin If n <= 1 then fib := n Else begin x := fib (n – 1) ; y := fib (n – 2) ; Fib := x + y ; End ; End ;
Latihan Buat fungsi barisan fibonacci sebagai fungsi yang iteratif. Narwen, M.Si / Jurusan Matematika FMIPA Unand
9
Catatan Kuliah
STRUKTUR DATA
4. Pencarian Secara Biner Pencarian secara binary adalah mencari posisi suatu bilangan pada barisan bilangan tertentu yang telah diurut dengan cara membagi dalam 2 bagian yang sama. Metode pencarian ini disebut Pencarian Biner atau Binary Search. Misalkan ada suatu array a yang sudah di urut secara ascending dengan indeks terendah “low = 1” dan tertinggi “high = indeks tertinggi”. Algoritma untuk menentukan indeks atau posisi dari elemen x di dalam array a adalah sebagai berikut:
Narwen, M.Si / Jurusan Matematika FMIPA Unand
10
Catatan Kuliah
STRUKTUR DATA
Function binsrch(a:arraytipe;n;indeks;x:integer):indeks; Function auxsrch(low,high:indeks):indeks ; var mid : indeks ; begin if low > high then auxsrch := 0 else begin mid := (low + high) div 2 ; if x = a[mid] then auxsrch := mid else if x < a[mid] then auxsrch := auxsrch (low, mid – 1) else auxsrch := (mid + 1, high) ; end ; end; begin binsrch := auxsrch (1, n) ; end ;
Narwen, M.Si / Jurusan Matematika FMIPA Unand
11
Catatan Kuliah
STRUKTUR DATA
Latihan Buat fungsi Binary Search sebagai fungsi yang iteratif. 5. Menara Hanoy Misalkan ada sebanyak n buah piringan yang diberi nomor 1, 2, …, n. Piringan tersebut disusun pada suatu tempat, misalkan tempat A, dengan urutan piringan bernomor yang terbesar berada di bawah piringan bernomor yang lebih kecil. Kalau piringan-piringan di A dipindahkan ke C dengan urutan yang sama, maka diperlukan B sebagai tempat penyimpanan sementara. Masalah ini dapat diselesaikan dengan menggunakan rekursif.
Narwen, M.Si / Jurusan Matematika FMIPA Unand
12
Catatan Kuliah
STRUKTUR DATA
Algoritmanya adalah sebagai berikut, 1. Jika n = 1, maka pindahkan piringan tunggal tersebut dari A → C dan berhenti 2. Jika n ≠ 1, maka pindahkan n – 1 teratas dari A → B, gunakan C sebagai penyimpanan sementara 3. Pindahkan sisanya dari A → C 4. Pindahkan n – 1 piringan dari B → C, gunakan A sebagai penyimpanan sementara.
Narwen, M.Si / Jurusan Matematika FMIPA Unand
13
Catatan Kuliah
STRUKTUR DATA
Bentuk procedure Pascal dari menara Hanoy adalah, Procedure towers(n:posInt;frompeg,topeg,auxpeg:char); Begin If n = 1 Then writeln(‘Move disk 1 from peg’,frompeg, ’to peg’,topeg) Else begin Towers (n–1, frompeg, auxpeg, topeg) ; Writeln (‘move disk’,n,’from peg’,frompeg, ’to peg’,topeg) ; Towers (n–1, auxpeg, topeg, frompeg) ; End ; End ;
Latihan Tentukan langkah-langkah untuk memindahkan 4 piringan dari A ke C. Narwen, M.Si / Jurusan Matematika FMIPA Unand
14
