Rekursi (recursion) adalah istilah yang digunakan dalam bidang matematika dan ilmu komputer, yang artinya adalah fungsi yang mendeskripsikan fungsi itu sendiri. Contoh dari rekursi dalam kehidupan sehari-hari adalah pada saat di dalam elevator ataupun sebuah ruangan yang memiliki cermin di dua sisi yang saling berhadapan 180⁰. Kedalaman rekursi ini tidaklah terbatas, maka dari itu dinamakan rekursi tak terbatas (Infinite Recursion).

Figure 1 Droste effect. Dalam gambar ini ada gambar ini lagi yang di dalamnya ada gambar ini lagi dan seterusnya sampai kedalaman tak terbatas

Dalam bidang komputer, atau lebih tepatnya ke bidang pemrograman, metode rekursi digunakan untuk menghitung suatu bilangan yang memiliki rumus berulang. Contohnya adalah faktorial sebuah bilangan. Bilangan tersebut akan dikalikan dengan bilangan sebelumnya sampai mencapai angka satu. Untuk itu, akan dipanggil rumus = N =N*(N-1) sampai N-1 adalah satu.

Faktorial dari 5

Faktorial dari 6

Contoh lain dari penggunaan metode rekursi dalam ilmu komputer adalah solusi Tower of Hanoi, penghitungan deret fibbonacci, fungsi Ackermann, dan lain-lain.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <iostream> typedef unsigned int UINT; long Factorial(UINT aNumber) { if (aNumber == 0) { return 1; } long result = 1; for (UINT i = 0; i < aNumber; i++) { result = result*(i + 1); } return result; } int main() { std::cout << Factorial(6); return 0; }

Potongan kode sumber di atas adalah penggunaan rekursi dalam mencari faktorial dari sebuah bilangan. Dalam kode di atas adalah faktorial dari 5 (5!).

Rekursi juga dapat bercabang-cabang. Jika dapat digambarkan, maka akan terlihat seperti pohon. Di mana cabang pertama terhubung dengan cabang kedua pada pangkalnya, lalu terhubung lagi ke cabang ketiga, dan seterusnya. Rekursi yang bercabang ini dapat kita gunakan untuk mencari kombinasi dari beberapa karakter atau apapun. Dalam fungsi rekursifnya terdapat perulangan yang menentukan berapa panjang dari kombinasi yang kita inginkan asal tidak melebihi panjang asal.

Metode stack ditemukan pada tahun 1955 dan dipatenkan pada tahun 1957 oleh Friedrich L. Bauer, seorang ilmuwan komputer asal Jerman. Sebagai sebuah tipe data abstrak, stack adalah tipe data yang berisi node-node dan memiliki beberapa operasi, diantaranya adalah push dan pop. Stack sendiri dapat dikatakan array of struct.

Stack biasa dilambangkan dengan blok-blok sel memori yang bertumpuk-tumpuk. Pointer menunjukkan lokasi tumpukan paling atas dari blok-blok tersebut. Operasi pada stack ini menggunakan metode LIFO (Last In First Out). Maksudnya adalah, yang berada pada tumpukan paling atas akan dikeluarkan terlebih dahulu. Metode sebaliknya (FIFO) digunakan pada queue.

Untuk menentukan jumlah maksimum stack, maka dideklarasikan konstanta MAX_STACK (atau variabel bernama apa saja yang dapat dijadikan sebagai jumlah maksimum stack). Elemen di dalam structnya adalah array data dan variabel yang menyatakan lokasi paling atas dari stack tersebut.

Figure 1 ilustrasi model stack

Operasi dalam stack

Push : Menambahkan node baru di atas tumpukan stack. Jika pointer menunjukkan lokasi paling atas dari tumpukan stack, maka pointer akan diupdate sebelum item (node) baru ditambahkan. Jika menunjukkan ke lokasi kosong di atas stack, maka pointer diupdate setelah node baru ditambahkan.

Pop : Menghilangkan node paling atas dan mengupdate pointer.

Clear : Mengosongkan stack.

IsEmpty : Untuk mengecek apakah stack kosong atau tidak.

IsFull : Mengecek apakah stack penuh atau tidak.

 

Definisi Queue

Secara harfiah, arti dari kata queue (berasal dari bahasa latin cauda {dibawa kepada masyarakat Inggris oleh orang Perancis}) adalah antrian. Sementara dalam istilah pemrograman artinya tidak jauh dari antrian. Berbeda dengan stack (tumpukan) yang menggunakan konsep LIFO (Last In First Out), konsep dari queue adalah FIFO (First In First Out), dimana data yang masuk lebih awal akan dikeluarkan terlebih dahulu.

Contoh konkret dari ADT (Abstract Data Type {tipe data abstrak} ) Queue adalah antrian pada loket bioskop. Yang mengantri terlebih dahulu akan dilayani dahulu.

Beberapa operasi dasar pada Queue pada C++ adalah:

Bool empty();

• Untuk mengecek apakah stack kosong atau tidak.

<tipe data> front();

• Untuk melihat data pada Queue terdepan. Metode ini me-return value.

Void pop(); / <tipe data> pop();

• Untuk mengeluarkan data pada Queue terdepan. Metode ini dapat dibuat me-return value.

Void push(<tipe data>);

• Untuk menambahkan data pada ujung Queue.

Int size();

• Untuk melihat dan mengembalikan nilai yang menunjukkan besar atau panjang Queue.

Java tidak secara spesifik memberi class khusus pada Queue. Untuk itu, kita harus menciptakan class tersendiri beserta metode-metodenya.

Deque

Di samping Queue, terdapat Deque. Deque adalah double-ended-Queue. Maksudnya adalah queue operasi penambahan dan pengambilan elemen dapat dilakukan pada kedua ujung Queue (baik depan maupun belakang, tapi tidak secara bersamaan).

Perbedaan implementasi Queue dengan Linked list dan Array

Array	Linked List
Dapat terjadi Underflow dan Overflow	Dapat terjadi Underflow dan Overflow (Overflow hanya akan terjadi saat memory dalam keadaan benar-benar penuh, jadi akan sangat langka terjadi)
Elemen yang dihapus harus diset ke null	Elemen yang dihapus tidak harus diset ke null

Linked List dalam Queue

Menambahkan node baru ke dalam Queue

Mengeluarkan node dari Queue

Matematika diskrit itu apa coba? pertama kali aku denger yang namanya matematika diskrit, yang aku pikirkan itu matematika yang bukan kalkulus. Dan memang iya. Yang namanya matematika diskrit tuh matematika logika gitu. Enggak asik banget deh…

Pelajarannya seperti ini: “Jika Anton mengerjakan pekerjaan rumah, maka dia tidak akan dimarahi oleh pak guru besok.” Itu adalah proposisi implikasi. –_-“ zzzzzz

Pokoknya gitu deh…

Nah, terus kita dapet pr. Aku kirain prnya dikit. Cuma 10 nomer aja kata si ibu dosen. Oke dah, aku kerjain aja nanti, mepet deadlinenya. Waktu aku buka bukunya, ya ampun, ternyata itu 10 nomer gila bener banyaknya. Senomer bisa sampe 6 subnomer (a-f). Gila bener!!! Mana pake Bahasa Inggris lagi bukunya. Susah banget… –_-“

Oh, iya. Untuk kedepannya, kata “gue” untuk ego penulis (hapsoro maksudnya ^^) bakal diganti sama “aku”. Biar lebih menggunakan Bahasa Indonesia aja sih. Soalnya Bahasa kita ini rasanya kurang membahana bahkan di dalam negeri sendiri. Bahasa Indonesia sudah mulai tergerus bahasa-bahasa asing karena, nampaknya, orang-orang di negeri ini lebih pede pake bahasa asing… (bukan berarti “gue” itu bahasa asing sih ^^)

Intinya, bakal ada banyak kata aku (atau bahkan mungkin “saya”) dalam blog ini! Sayonara~ sampai bertemu di tulisan berikutnya! ^^