rekursif

Pengertian Rekursif

  Rekursif dapat diartikan bahwa suatu proses yang  bisa memanggil dirinya sendiri. sedikit menyimpang dari pengertian ada sedikit pendapat tentang Rekursif salah satunya adalah Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.

Contoh Rekursif

Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:

def kali(a, b):


    return a if b == 1 else a + kali(a, b - 1)

Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintaha + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:

kali(2, 4)


  -> 2 + kali(2, 3)

  -> 2 + (2 + kali(2, 2))

  -> 2 + (2 + (2 + kali(2, 1)))
-> 2 + (2 + (2 + 2))

 + 6
  -> 8
-> 2 + (2 + 4)
  -> 

2

Perhatikan bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti ([Math Processing Error]). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan perhitungan faktorial:

def faktorial(n):


    return n if n == 1 else n * faktorial(n - 1)

Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil dan lihat langkah pemanggilannya:

faktorial(5)


  -> 5 * faktorial(4)

  -> 5 * (4 * faktorial(3))

  -> 5 * (4 * (3 * faktorial(2)))

  -> 5 * (4 * (3 * (2 * faktorial(1))))
-> 5 * (4 * (3 * (2 * 1)))

 * (4 * 6)
  -> 5 * 24
-> 5 * (4 * (3 * 2))
  -> 
5

-> 120

Dengan melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:

1. Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2. Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.

Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.

Contoh Program C++

Menghitung Faktorial

#include <iostream>

using namespace std;

long int faktorial (int n)

{ if (n==0 || n==1)

    return 1;

else

   return n* faktorial (n-1);}

int main()

{ int n;

long int hasil;

cout<<"Masukkan nilai yang ingin di faktorialkan. n=  ";

cin>>n;

hasil=faktorial(n);

cout<<n<< "!=  "<< hasil;

return 0;

}

Daftar Pustaka

Wordpress.(2011),”Rekursif dan Iteratif ”. http://einzebern.wordpress.com/2011/10/26/rekursif-dan-iteratif/ (diakses 12,April,2014)

 Bertzzie(2013), "Analisis Algoritma ". http://bertzzie.com/knowledge/analisis-algoritma/Rekursif.html (diakses 12,April,2014)

selection sort

Pengertian Selection Sort

Selection Sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan, Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

CONTOH :

Data Acak    : 5 6 8 1 3 25 10

Ascending    : 1 3 5 6 8 10 25

Descending    : 25 10 8 6 5 3 1

Konsep Selection Sort Algoritma pengurutan sederhana salah satunya adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut,  disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar. Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu.

Contoh Selection Sort :

Ascending

• Cek seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)

• Temukan nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada pada posisi kedua (10).

• Dua elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan nilai terkecil pertama dan kedua dalam array tsb.

• Sekarang, ulangi dengan cara/proses “pilih dan tukar”

• Pengurutan Selesai.

CONTOH PROGRAM

#include <iostream>

using namespace std;

void tampilkanLarik(int data[], int n)

{

    int i;

    for (i=0; i<n; i++)

        cout<< data[i]<<" ";

        cout<<endl;

}

void selection_sort(int data[], int n)

{

    int posMin, posAwal, j, temp;

    for (posAwal=0; posAwal < n-1; posAwal++)

    {

        posMin = posAwal;

        for ( j=posAwal+1; j<n; j++)

            if (data[posMin] > data[j])

                posMin=j;

            temp=data[posAwal];

            data[posAwal]=data[posMin];

            data[posMin]=temp;

            cout<< "\nHasil posAwal= "<< posAwal <<": ";

            tampilkanLarik(data,n);

        }

    }

int main()

{

   const int JUM_DATA =10;

   int i;

   int data[] = {9,13,17,89,23,90,45,87,56,32};

   selection_sort(data, JUM_DATA);

   cout<<"\nHasil Pengurutan : ";

   tampilkanLarik(data,JUM_DATA);

    return 0;

}