Algoritma Rekursif

Rekursif

Hai sobat blogger kali ini saya kita membahas “Rekursif”. Sebenarnya tugas ini adalah tugas dari dosen, tapi biar bisa lebih berguna makanya saya mencoba untuk mengeshare disini.

Rekursif berarti suatu proses yang memanggil dirinya sendiri. Dalam rekursif sebenarnya terkandung pengertian prosedur atau fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi. Rekursif merupakan teknik pemrograman yang penting, dan beberapa bahasa pemrograman modern mendukung keberadaan proses rekursif ini.

Pemanggilan prosedur atau fungsi ke dirinya sendiri bisa berarti proses yang berulang yang tidak bisa diketahui kapan akan berakhir. Dalam pemakaian sehari-hari, rekursi merupakan teknik pemrograman yang berdaya guna untuk digunakan pada pekerjaan pemrograman dengan mengeksperisikannya ke dalam suku-suku dari program lain dengan menambahkan langkahlangkah sejenis. Contoh paling sederhana dari proses rekursi adalah menghitung nilai faktorial dari bilangan bulat. Nilai faktorial, secara rekursif dapat ditulis sebagai :

0! = 1

N! = N x (N-1)!, Untuk N > 0

yang secara notasi pemrograman bisa ditulis sebagai:

FAKTORIAL (0) = 1 1)

FAKTORIAL (N) = N * FAKTORIAL (N-1) 2)

Persamaan 2) di atas merupakan contoh hubungan rekurens (recurrence relation), yang berarti bahwa nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil. Persamaan 1) yang tidak bersifat rekursif, disebut nilai awal. Setiap fungsi rekursi paling sedikit mempuyai 1 (satu) nilai awal; jika tidak, fungsi tersebut tidak bisa dihitung secara eksplisit.

Proses rekursi akan selesai , ini terletak pada kondisi pernyataan if-nya. Jika pernyataan if menjadi FALSE maka akan menghentikan proses rekursi
Prinsif dan proses rekursi:

1. Memiliki kasus non rekursi(sederhana)
2. Kasus awal diarahkan menuju kasus sederhana
3. Mendefinisikan proses rekursi

Dalam bentuk pernyataan , biasanya menggunakan pernyataan if( atau if……else)
Contoh  program rekursi sederhana dengan DEV C++

#include <iostream>
using namespace std;
void cetak(int n)
{
if(n<=4)
cetak(n+1);
cout<<n<<endl;
}

int main(int argc, char *argv[])
{
cout<<“Hasil dengan cara menggunakan rekursif: “;
cetak(1);
system(“PAUSE”);
return EXIT_SUCCESS;
}

 

Fungsi yang didefinisikan secara rekursif:

Langkah-langkah untuk mendefinisikan fungsi dengan domain bilangan cacah:

1. Langkah basis: Definisikan nilai fungsi pada saat nol.
2. Langkah rekursif: Berikan aturan untuk mencari nilai fungs iuntuk setiap bilangan bulat berdasarkan nilai fungsi pada bilangan bulat yang lebih kecil.

Definisi seperti itu disebut rekursif atau definisi induktif.

Bentuk rekursif :

a. suatu subrutin/fungsi/ prosedur yang memanggil dirinya sendiri.
b. Bentuk dimana pemanggilan subrutin terdapat dalam body subrutin
c. Dengan rekursi, program akan lebih mudah dilihat

Bentuk rekursi bertujuan untuk : b.menyederhanakan penulisan program c.menggantikan bentuk iterasi Syarat bentuk rekursif:  ada kondisi terminal (basis)  ada subroutine call yang melibatkan parameter yang nilainya menuju kondisi terminal (recurrence)

Proses Rekursif

Untuk memahami proses rekursif yang terjadi dalam sebuah fungsi rekursif, perhatikan contoh sederhana di bawah ini. Contoh di bawah ini menyajikan satu fungsi untuk menghitung harga pangkat suatu nilai bilangan bulat misalnya 3⁵, berdasarkan hubungan rekurens seperti dijelaskan diatas, maka proses rekursif akan tampak pada gambar berikut ini:

Gambar:  Ilustrasi Penghitungan pangkat secara rekursif

Dari definisi tersebut, statemen pertama menunjukkan nilai yang utama dari fungsi, dan statemen kedua menunjukan perulangan penurunan dari n yaitu n-1.

Selain fungsi, prosedur juga dapat dilakukan operasi rekursif. Sebagai contoh penggunaan proses rekursif pada prosedur adalah prosedur pencarian biner (binary search). Dalam beberapa hal rekursif kurang efisien dibandng proses iterasi. Dalam artian pemecahan secara rekursif dan secara iterasi mempunyai keuntungan dan kekurangan yang bisa saling diperbandingkan. Adalah cukup sulit untuk menentukan mana yang paling sederhana, paling jelas, paling efisien dan paling

mudah dibanding yang lain. Bisa ditambahkan, pemilihan secara iteratif maupun rekursif boleh dikatakan merupakan kesenangan seorang programmer sesuai dengan keinginannya.

Kelebihan perulangan rekursif
Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar
Dapat melakukan perulangan dengan batasan fungsi

Kekurangan perulangan rekursif
Tidak bisa melakukan nested loop atau looping bersarang.
Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja.
Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack dan ada kalaya akan menyebabkan stack tak cukup lagi (Stack Overum).
Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk.