RSS

FUNGSI REKURSIF

17 May

Rekursi adalah teknik yang mengarah ke solusi elegan untuk masalah yang sulit program Menggunakan loop sederhana. Misalkan Anda ingin mencari semua file di bawah direktori yang berisi kata tertentu. Bagaimana Anda memecahkan masalah ini? Ada beberapa cara untuk melakukannya. Sebuah solusi intuitif dan efektif adalah menggunakan rekursi dengan mencari file dalam subdirektori secara rekursif.

H-pohon, digambarkan dalam Gambar 20.1, yang digunakan dalam integrasi (VLSI) desain yang sangat besar sebagai jam jaringan distribusi untuk routing sinyal waktu ke seluruh bagian chip dengan  propagasi penundaan yang sama . Bagaimana Anda menulis sebuah program untuk menampilkan H-pohon? Pendekatan yang baik adalah dengan menggunakan rekursi.

GB 1

Untuk menggunakan rekursi adalah untuk program menggunakan metode rekursif-yaitu, menggunakan metode yang memanggil diri mereka sendiri. Rekursi adalah teknik pemrograman yang berguna. Dalam beberapa kasus, memungkinkan  Anda untuk mengembangkan solusi  yang alami, mudah, sederhana untuk masalah yang tadinya sulit. Bab ini memperkenalkan konsep dan teknik pemrograman rekursif dan menggambarkan  dengan contoh bagaimana untuk “berpikir secara rekursif.”

Studi Kasus: menghitung faktorial

Sebuah metode rekursif adalah salah satu yang memanggil dirinya sendiri. Banyak fungsi matematika yang didefinisikan menggunakan rekursi. Mari kita mulai dengan contoh sederhana. Faktorial dari n bilangan dapat rekursif didefinisikan sebagai berikut:

0! = 1;
n! = n × (n – 1), n> 0!

Bagaimana Anda menemukan n! untuk n yang diberikan? Untuk menemukan 1! mudah, karena Anda tahu bahwa 0! adalah 1, dan 1! = 1 × 0!. Dengan asumsi bahwa Anda tahu (n – 1)!, Anda dapat memperoleh n! segera dengan menggunakan n × (n – 1)!. Dengan demikian, masalah komputasi n! direduksi menjadi komputasi (n – 1)!. Ketika komputasi (n – 1)!, Anda dapat menerapkan ide yang sama secara rekursif sampai n dikurangi menjadi 0.

Mari faktorial (n) menjadi metode untuk komputasi n!. Jika Anda memanggil metode dengan n = 0, segera mengembalikan hasilnya. Metode ini tahu bagaimana untuk memecahkan kasus yang paling sederhana, yaitu disebut sebagai kasus dasar atau kondisi berhenti. Jika Anda memanggil metode dengan n> 0, itu mengurangi masalah menjadi subproblem untuk menghitung faktorial dari n – 1. Subproblem pada dasarnya sama dengan masalah asli, tapi lebih sederhana atau lebih kecil. Karena subproblem yang memiliki properti yang sama sebagai masalah asli, Anda dapat memanggil metode dengan berbeda argumen, yang disebut sebagai panggilan rekursif. Algoritma rekursif untuk menghitung faktorial (n) secara sederhana dapat digambarkan sebagai berikut:

if (n == 0)
return  1;

else

return n * factorial(n – 1);

A recursive call can result in many more recursive calls, because the method keeps pada membagi subproblem ke dalam submasalah baru. Untuk metode rekursif untuk mengakhiri, masalah akhirnya harus dikurangi dengan kasus berhenti, di mana titik metode mengembalikan hasil ke pemanggil nya. Pemanggil kemudian melakukan perhitungan dan mengembalikan  mengakibatkan pemanggil  sendiri. Proses ini berlanjut sampai hasilnya dikirimkan kembali ke aslinya pemanggil. Masalah asli sekarang dapat diselesaikan dengan mengalikan n dengan hasil faktorial (n – 1).

Listing 20.1 memberikan program lengkap yang meminta pengguna untuk memasukkan bilangan bulat positif  dan menampilkan faktorial untuk nomor tersebut.

GB2

Metode faktorial (baris 16-21) pada dasarnya adalah terjemahan langsung dari rekursif
Definisi matematika untuk faktorial ke dalam kode Java. Panggilan untuk faktorial rekursif
karena itu menyebut dirinya. Parameter dilewatkan ke pengurangan faktorial hingga mencapai
kasus dasar dari 0.

Anda tahu bagaimana menulis sebuah metode rekursif. Bagaimana rekursi kerja? Gambar 20.2 mengilustrasikan pelaksanaan panggilan rekursif, dimulai dengan n = 4. Penggunaan ruang stack untuk rekursif  panggilan ditunjukkan pada Gambar 20.3.

GB3GB4

Hal ini lebih sederhana dan lebih efisien untuk menerapkan metode faktorial menggunakan loop.
Namun, kami menggunakan metode faktorial rekursif sini untuk menunjukkan konsep rekursi. Kemudian dalam bab ini, kami akan menyajikan beberapa masalah yang inheren rekursif dan sulit untuk dipecahkan tanpa menggunakan rekursi. Jika rekursi tidak mengurangi masalah dengan cara yang memungkinkan untuk akhirnya bertemu  ke kasus dasar, rekursi tak terbatas dapat terjadi.

Contoh yang dibahas dalam bagian ini menunjukkan metode rekursif yang memanggil dirinya sendiri. Ini dikenal sebagai rekursi langsung. Hal ini juga memungkinkan untuk membuat rekursi tidak langsung. Hal ini terjadi ketika sebuah metode memanggil metode B, yang pada gilirannya memanggil metode A. Bahkan terdapat beberapa lagi metode yang terlibat dalam rekursi. Sebagai contoh, metode A memanggil metode B, yang memanggil Metode C, yang memanggil metode A.

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 35, berdasarkan hubungan rekurens seperti dijelaskan diatas, maka proses rekursif akan tampak pada gambar berikut ini :

GB5

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.

GB6

 Studi Kasus: Komputasi Bilangan Fibonacci

Dalam beberapa kasus, rekursi memungkinkan Anda untuk membuat sebuah solusiyang intuitif, mudah, sederhana  untuk suatu masalah.  Metode faktorial di bagian sebelumnya dapat dengan mudah ditulis ulang tanpa menggunakan rekursi. Pada bagian ini, kita menunjukkan contoh untuk menciptakan solusi intuitif untuk masalah menggunakan rekursi. Pertimbangkan terkenal masalah Fibonacci-series:

Seri        :               0   1   1   2   3   5   8   13   21   34   55   89  . . .
indeks   :               0   1   2   3   4   5   6     7     8     9    10   11

Seri Fibonacci dimulai dengan 0 dan 1, dan setiap nomor berikutnya adalah jumlah dari sebelumnya
dua. Serial ini dapat rekursif didefinisikan sebagai:

GB7

Seri Fibonacci bernama untuk Leonardo Fibonacci, seorang matematikawan abad pertengahan, yang   berasal itu untuk model pertumbuhan populasi kelinci. Hal ini dapat diterapkan dalam optimasi numerik dan di berbagai daerah lainnya.
Bagaimana Anda menemukan fib (indeks) untuk indeks yang diberikan? Sangat mudah untuk menemukan fib (2), karena Anda tahu fib (0) dan fib (1). Dengan asumsi bahwa Anda tahu fib (index – 2) dan fib (indeks – 1), Anda dapat memperoleh fib (indeks) segera. Dengan demikian, masalah komputasi fib (indeks) adalah dikurangi menjadi komputasi fib (index – 2) dan fib (indeks – 1). Ketika melakukannya, Anda menerapkan Ide rekursif sampai indeks dikurangi menjadi 0 atau 1.
Kasus dasar adalah indeks = 0 atau indeks = 1. Jika Anda memanggil metode dengan indeks = 0 atau  index = 1, segera mengembalikan hasilnya. Jika Anda memanggil metode dengan indeks> = 2, membagi  masalah menjadi dua submasalah untuk komputasi fib (index – 1) dan fib (index – 2) menggunakan panggilan rekursif. Algoritma rekursif untuk komputasi fib (indeks) bisa dengan sederhana dijelaskan sebagai berikut:

GB7GB8

Program ini tidak menunjukkan jumlah yang cukup besar pekerjaan dilakukan di belakang layar oleh  komputer. Gambar 20.4, bagaimanapun, menunjukkan panggilan rekursif beruntun untuk mengevaluasi fib (4).
Metode asli, fib (4), membuat dua panggilan rekursif, fib (3) dan fib (2), dan kemudian
kembali fib (3) + fib (2). Tapi dalam rangka apa yang disebut metode ini? Di Jawa, operan
dievaluasi dari kiri ke kanan, sehingga fib (2) disebut setelah fib (3) benar-benar dievaluasi. Itu
label pada Gambar 20.4 menunjukkan urutan di mana metode yang dipanggil.

gb9

Seperti yang  ditunjukkan pada Gambar 20.4, ada banyak panggilan rekursif digandakan.

Misalnya, fib (2)  disebut dua kali, fib (1) tiga kali, dan fib (0) dua kali. Secara umum, komputasi fib (indeks) membutuhkan sekitar dua kali lebih banyak panggilan rekursif seperti halnya komputasi fib (index – 1). Ketika Anda mencoba nilai indeks yang lebih besar, jumlah panggilan secara substansial meningkat, seperti yang ditunjukkan pada Tabel 20.1.

Rekursif penerapan metode fib sangat sederhana dan mudah, tetapi tidak efisien, karena memerlukan lebih banyak waktu dan memori untuk menjalankan metode rekursif. Lihat Pemrograman Latihan 20.2 untuk solusi yang efisien menggunakan loop. Meskipun tidak praktis, metode fib rekursif adalah contoh yang baik tentang bagaimana untuk menulis metode rekursif.

sumber : Introduction to Java Programming 9th Edition by Y Daniel Liang dan Modul Praktikum Algoritma & Pemrograman II

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: