Fungsi Rekursif & Fungsi Iteratif

A. Fungsi Rekursif

Fungsi rekursif merupakan fungsi yang memanggil dirinya sendiri, prosesnya terjadi secara berulang-ulang. Perulangan rekursif menggunakan if.
Contoh :
f(0) = 3
f(n+1) = 2 f(n) + 3
f(3) ....?
Maka  f(0) = 3

           f(1) → f(n + 1) = 2 f(n) + 3
                        f(0 + 1) = 2 f(0) + 3
                        f(1) = 2.3 + 3 = 9
           f(2) → f(1 + 1) = 2 f(1) + 3
                        f(2) = 2.9 + 3 = 21
           f(3) → f(2 + 1) = 2 f(2) + 3
                        f(2) = 2.21 + 3 = 45

B. Fungsi Iteratif

Fungsi iteratif merupakan perulangan terhadap sekelompok instruksi dimana perulangan akan berhenti jika batasan syarat sudah tidak terpenuhi. Perulangan iteratif menggunakan for, while, do-while.

Kasus :
FPB (Faktor Persekutuan Terbesar)
Misal FPB 228 dan 90 :
228 / 90 = 2 sisa 48
90 / 48   = 1 sisa 42
48 / 42   = 1 sisa 6
42 / 6     = 7 sisa 0
FPB adalah sisa terakhir sebelum sisa = 0, yaitu 6.

Penyelesaian dengan fungsi rekursif 
Ilustrasi FPB rekursif :
FPB(228,90)    m > n
FPB(48,90)      m < n
FPB(90,48)      m > n
FPB(42,48)      m < n
FPB(48,42)      m > n
FPB(6,42)        m < n
FPB(42,6)        m > n
FPB(0,6)          m = 0
FPB 228 dan 90 = 6

int FPB(int m, int n){
       if (m == 0) return n;
       else if (m < n) return FPB(n, m);
       else return FPB(m % n, n);
}

Penyelesaian dengan fungsi iteratif 
m = 228, n = 90
do{
       r = m % n;
       if (r != 0){
              m = n;
              n = r;
       }
} while (r !=  0);

Graph

Graph (graf) merupakan struktur data yang terdiri atas kumpulan vertex (V) dan edge (E).
G = (V, E)
V : himpunan tidak kosong dari simpul-simpul
E : himpunan sisi (edge) yang menghubungkan sepasang simpul

Terdapat 2 kategori graf :
1. Directed graph (Graf berarah), seperti G3.
2. Undirected graph (Graf tidak berarah), seperti G1 dan G2.

Pada graf tersebut dapat didefinisikan himpunan vertex dan himpunan edge sebagai berikut:
V(G1) = {1, 2, 3, 4}                E(G1) = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
V(G2) = {1, 2, 3, 4, 5, 6, 7}    E(G2) = {(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)}
V(G3) = {1, 2, 3}                    E(G3) = {(1,2), (2,1), (2,3)}

Terminologi Graf

1. Adjacent (Ketetanggaan)
Dua simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau G1 : Simpul 1 bertetangga dengan simpul 2 dan 3
                   Simpul 1 tidak bertetangga dengan simpul 4

2. Incidency (Bersisian)
Tinjau G1 : Sisi (2,3) bersisian dengan simpul 2 dan simpul 3
                   Sisi (2,4) bersisian dengan simpul 2 dan simpul 4
                   Sisi (1,2) tidak bersisian dengan simpul 4

3. Isolated Vertex (Simpul Terpencil)
Tinjau G3 : Simpul 5 adalah simpul terpencil

4. Degree (Derajat)
Degree suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Tinjau G1 : d(1) = d(4) = 2
                   d(2) = d(3) = 3
Tinjau G2 : d(1) = 3 → bersisian dengan sisi ganda
                   d(4) = 1 → bersisian dengan sisi gelang (loop)
Tinjau G3 : d(5) = 0 → simpul terpencil

                   d(4) = 1 → simpul anting-anting (pendant vertex)

Minimum Spanning Tree

Pada graf tak berbobot, minimum spanning tree adalah jalur dengan jumlah edge minimum sehingga semua vertex bisa dicapai.

Pada graf ABCDE terdapat 10 jaring yang menghubungkan kelima vertex, namun sebenarnya dibutuhkan hanya 4 jaring untuk mengunjungi setiap vertex yang ada pada graf tersebut, yaitu AB BC CD DE. Jalur minimum inilah yang disebut sebagai minimum spanning tree.
E = V - 1
Sehingga bila ada 5 vertex maka hanya dibutuhkan 4 edge untuk menghubungkan semua vertex tersebut.

Algoritma Djikstra

Algoritma djikstra adalah algoritma untuk mencari jalur terpendek dari vertex awal ke vertex akhir.

Jalur terpendek : A - B - F - C - H dengan jarak 60.

AVL Tree

AVL Tree adalah binary search tree yang memiliki selisih tingkat antara subtree kiri dan subtree kanan maksimal 1. AVL tree bertujuan untuk menyeimbangkan binary search tree.
Untuk menyeimbangkan tree dilakukan rotasi berikut :
1. Single rotation (Jika letak subtree Left- Left atau Right-Right)
2. Double Rotation (Jika letak subtree Left-Right atau Right-Left)

Binary Tree

Syarat Binary Tree (Pohon Biner)

#  Setiap node hanya boleh memiliki maksimal 2 subtree, kedua subtree harus terpisah

#  Setiap node hanya boleh memiliki paling banyak 2 child

Jumlah maksimum node pada setiap tingkat = 2 ^{n - 1}

Jumlah maksimum node pada binary tree = 2 ⁿ - 1

n : tingkat

Contoh pada gambar disamping :
Jumlah maksimum node tingkat 1 = 2^{n - 1} = 2^{1 – 1} = 1

Jumlah maksimum node tingkat 2 = 2^{n - 1} = 2^{2 – 1} = 2

Jumlah maksimum node tingkat 3 = 2^{n - 1} = 2^{3 – 1} = 4

Jumlah maksimum node binary tree dengan 3 tingkat
= 2ⁿ – 1 = 2³ – 1 = 7

Operasi-operasi Tree

1. Insert

Menambah node ke dalam tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan. Jika data yang akan dimasukkan lebih kecil daripada elemen root, maka akan diletakkan di node sebelah kiri.

2. Find

Mencari node di dalam tree secara rekursif sampai node ditemukan. Syaratnya tree tidak boleh kosong.

3. Traverse

Kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.

4. Count

Menghitung jumlah node dalam tree.

5. Height

Mengetahui kedalaman sebuah tree.

6. Find Min dan Find Max

Mencari nilai terkecil dan terbesar pada tree.

7. Child

Mengetahui anak dari sebuah node (Jika punya).

Ilustrasi Insert

Soal 1
Buatlah sebuah pohon dari urutan node berikut :
8  9  11  15  19  20  21  7  3  2  1  5  6  4  13  14  10  12  17  16  18

Jenis Traverse (Kunjungan)
1. PreOrder
Cetak node yang dikunjungi, kunjungi left, kunjungi right.



















2. InOrder
Kunjungi left, cetak node yang dikunjungi, kunjungi right.

3. PostOrder
Kunjungi left, kunjungi riht, cetak node yang dikunjungi.

Contoh Implementasi :

\











Soal 2
Tentukan notasi prefix, infix, dan postfix dari ekspresi berikut :

Jawaban :
Prefix   : ^ - * + ABC - DE + FG
Infix     : ((A + B) * C - (D - E)) ^ (F + G)
Postfix : AB + C * DE - - FG + ^

Soal 3
Tentukan notasi prefix, infix, dan postfix dari ekspresi berikut :

Jawaban :

Prefix   : - ^ / - * 4 A B C D * / 1/2 ^ - E F 2
Infix     : ((((4 * A) - B) / (C * D)) ^ 1/2) - ((E - F) ^ 2)
Postfix : 4 A * B - C D * / 1/2 ^ E F - 2 ^ -

Soal 4 (UAS Struktur Data 2013/2014 Informatika UNDIP)
Diketahui A = 7, B = 4, C = 3, D = -2, E = 5
Hitung ekspresi prefix berikut :
a) * + A B - C D
b) / + * A B C - D E

Jawaban :
a) * + A B - C D = (A + B) * (C - D) = (7 + 4) * (3 - (-2)) = 55
b) / + * A B C - D E = ((A * B) + C) / (D - E) = ((7 * 4) + 3) / (-2 - 5) = -4,43


Metode Pencarian Node

1. Depth First Search (DFS)
Urutan pencarian : A-B-D-E-C-F-G

2. Breadth First Search (BFS)
Urutan pencarian : A-B-C-D-E-F-G




Penghapusan (Delete) Node
1. Jika yang di delete adalah leaf, maka bisa langsung di delete

2. Jika node yang di delete hanya memiliki satu anak, maka anak tersebut langsung menggantikan posisi parent-nya.

3. Jika yang di delete adalah node dengan 2 anak (subtree), maka node yang menggantikan node yang dihapus adalah :
#  Node yang akan dihapus adalah node (30), berada di sisi kiri.
#  Node yang ada di sisi kanan dari node yang akan dihapus adalah (40).
#  Telusuri sisi kiri, node (35).
    Sisi kiri (35) tidak ada (null), maka (35) menjadi induk dari (40).
#  Sisi kanan dari node (35) adalah (37), maka (37) menjadi sisi kiri dari node (40).
#  Sisi kanan dari node (40) adalah (45), posisinya tetap.

Penyajian Binary Tree Secara Berurutan

Tree

Tree merupakan kumpulan node yang saling terhubung satu sama lain dalam satu kesatuan yang membentuk layaknya struktur sebuah pohon.

A. Representasi Tree

1. Tree dan Tingkatannya

2. Diagram Venn

3. Notasi Tingkat

4. Notasi Kurung
A (B (D , E (I , J)), C ( F , G , H))

B. Terminologi Tree

Istilah	Arti
Predecesor	Node yang berada di atas node tertentu
Successor	Node yang berada di bawah node tertentu
Ancestor	Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Descendant	Seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama
Parent	Predecesor satu level di atas suatu node
Child	Successor satu level di bawah suatu node
Sibling	Node-node yang memiliki parent yang sama
Subtree	Suatu node beserta descendant-nya
Size	Banyaknya node dalam tree
Height	Banyaknya tingkatan dalam tree
Root	Node khusus yang tidak memiliki predecesor
Leaf	Node-node dalam tree yang tidak memiliki successor
Degree	Banyaknya child dalam suatu node

Penjelasan tentang tree :

   Ancestor (F) = C, A

   Descendant (C) = F, G

   Parent (D) = B

   Child (A) = B, C

   Sibling (F) = G

   Size = 7

   Height = 3

   Root = A

   Leaf = D, E, F, G

   Degree (C) = 2