Tutorial ini menjelaskan apa itu Rekursi dengan Contoh, Jenis, dan Konsep Terkait. Tutorial ini juga mencakup Rekursi Vs Iterasi:
Dari tutorial sebelumnya di Java, kita telah melihat pendekatan iteratif di mana kita mendeklarasikan sebuah loop dan kemudian menelusuri struktur data secara berulang dengan mengambil satu elemen pada satu waktu.
Kita juga telah melihat aliran bersyarat di mana sekali lagi kita menyimpan satu variabel perulangan dan mengulangi sepotong kode sampai variabel perulangan memenuhi kondisi tersebut. Dalam hal pemanggilan fungsi, kita telah mengeksplorasi pendekatan berulang untuk pemanggilan fungsi juga.
Dalam tutorial ini, kita akan membahas pendekatan yang berbeda dalam pemrograman, yaitu pendekatan Rekursif.
Apa Itu Rekursi Di Jawa?
Rekursi adalah proses di mana sebuah fungsi atau metode memanggil dirinya sendiri berulang kali. Fungsi yang dipanggil berulang kali baik secara langsung maupun tidak langsung disebut "fungsi rekursif".
Kita akan melihat berbagai contoh untuk memahami rekursi. Sekarang mari kita lihat sintaks rekursi.
Sintaks Rekursi
Setiap metode yang mengimplementasikan Pengulangan memiliki dua bagian dasar:
- Pemanggilan metode yang dapat memanggil dirinya sendiri, yaitu rekursif
- Prasyarat yang akan menghentikan pengulangan.
Perhatikan bahwa sebuah prasyarat diperlukan untuk metode rekursif karena, jika kita tidak menghentikan rekursi maka rekursi akan terus berjalan tanpa batas dan mengakibatkan stack overflow.
Sintaks umum rekursi adalah sebagai berikut:
methodName (T parameter...) { if (kondisi awal == true) //kondisi awal atau kondisi dasar { kembalikan hasil; } return methodName (T parameter...); //panggilan rekursif } Perhatikan bahwa kondisi awal juga disebut kondisi dasar. Kita akan membahas lebih lanjut tentang kondisi dasar di bagian selanjutnya.
Memahami Rekursi Di Jawa
Pada bagian ini, kita akan mencoba untuk memahami proses rekursi dan melihat bagaimana proses tersebut terjadi. Kita akan belajar tentang kondisi dasar, stack overflow, dan melihat bagaimana sebuah masalah dapat diselesaikan dengan rekursi dan detail lainnya.
Kondisi Dasar Rekursi
Ketika menulis program rekursif, pertama-tama kita harus menyediakan solusi untuk kasus dasar, kemudian kita mengekspresikan masalah yang lebih besar dalam bentuk masalah-masalah yang lebih kecil.
Sebagai seorang contoh, kita dapat mengambil masalah klasik dalam menghitung faktorial sebuah bilangan. Diberikan sebuah bilangan n, kita harus menemukan faktorial dari n yang dilambangkan dengan n!
Sekarang mari kita implementasikan program untuk menghitung faktorial n (n!) menggunakan rekursi.
public class Main{ static int fakta(int n) { if (n == 1) // kondisi dasar kembalikan 1; else kembalikan n*fakta(n-1); } public static void main(String[] args) { int hasil = fakta(10); System.out.println("10! = " + hasil); } } Keluaran
Pada program ini, kita dapat melihat bahwa kondisi (n<=1) adalah kondisi dasar dan ketika kondisi ini tercapai, fungsi akan mengembalikan 1. Bagian else pada fungsi tersebut adalah pemanggilan rekursif. Tetapi setiap kali metode rekursif dipanggil, n akan dikurangi 1.
Dengan demikian kita dapat menyimpulkan bahwa pada akhirnya nilai n akan menjadi 1 atau kurang dari 1 dan pada titik ini, metode akan mengembalikan nilai 1. Kondisi dasar ini akan tercapai dan fungsi akan berhenti. Perhatikan bahwa nilai n dapat berupa apa saja selama memenuhi kondisi dasar.
Pemecahan Masalah Menggunakan Rekursi
Ide dasar di balik penggunaan rekursi adalah untuk mengekspresikan masalah yang lebih besar ke dalam masalah-masalah yang lebih kecil, dan kita perlu menambahkan satu atau lebih kondisi dasar agar kita dapat keluar dari rekursi.
Hal ini telah ditunjukkan pada contoh faktorial di atas. Pada program ini, kita mengekspresikan faktorial n (n!) dalam bentuk nilai yang lebih kecil dan memiliki kondisi awal (n & lt;=1) sehingga ketika n mencapai 1, kita dapat keluar dari metode rekursif.
Kesalahan Stack Overflow Dalam Rekursi
Kita tahu bahwa ketika metode atau fungsi dipanggil, status dari fungsi tersebut disimpan di stack dan diambil ketika fungsi tersebut kembali. Stack juga digunakan untuk metode rekursif.
Tetapi dalam kasus rekursi, masalah dapat terjadi jika kita tidak mendefinisikan kondisi dasar atau ketika kondisi dasar entah bagaimana tidak tercapai atau dieksekusi. Jika situasi ini terjadi maka stack overflow dapat muncul.
Mari kita pertimbangkan contoh notasi faktorial di bawah ini.
Di sini kita telah memberikan kondisi dasar yang salah, n==100.
public class Main { static int fakta(int n) { if (n == 100) // kondisi dasar yang mengakibatkan stack overflow return 1; else return n*fakta(n-1); } public static void main(String[] args) { int hasil = fakta(10); System.out.println("10! = " + hasil); } } Jadi, ketika n & gt; 100, metode akan mengembalikan 1 tetapi rekursi tidak akan berhenti. Nilai n akan terus berkurang tanpa batas waktu karena tidak ada kondisi lain yang menghentikannya. Hal ini akan terus berlanjut hingga tumpukan meluap.
Kasus lainnya adalah ketika nilai n <100. Dalam kasus ini, metode ini juga tidak akan pernah mengeksekusi kondisi dasar dan mengakibatkan stack overflow.
Contoh Rekursi di Java
Pada bagian ini, kita akan mengimplementasikan contoh-contoh berikut dengan menggunakan rekursi.
#1) Deret Fibonacci Menggunakan Rekursi
Deret Fibonacci diberikan oleh,
1,1,2,3,5,8,13,21,34,55,…
Urutan di atas menunjukkan bahwa elemen saat ini adalah jumlah dari dua elemen sebelumnya. Selain itu, elemen pertama dalam deret Fibonacci adalah 1.
Jadi secara umum, jika n adalah angka saat ini, maka angka tersebut diberikan oleh jumlah (n-1) dan (n-2). Karena elemen saat ini dinyatakan dalam bentuk elemen sebelumnya, kita dapat mengekspresikan masalah ini dengan menggunakan rekursi.
Program untuk mengimplementasikan deret Fibonacci diberikan di bawah ini:
public class Main { // metode untuk menghitung deret fibonacci static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1 + fibonacci(n-2); } public static void main(String[] args) { int angka = 10; //cetak 10 angka pertama deret fibonacci System.out.println ("Deret Fibonacci: 10 angka pertama: "); for (int i = 1; i <= angka; i++) { System.out.print(fibonacci(i) + " ");} } } Keluaran
#2) Memeriksa Apakah Suatu Bilangan adalah Palindrom Menggunakan Perulangan
Palindrom adalah urutan yang sama ketika kita membacanya dari kiri ke kanan atau kanan ke kiri.
Diberikan sebuah angka 121, kita melihat bahwa ketika kita membacanya dari kiri ke kanan dan kanan ke kiri, angka tersebut sama. Oleh karena itu, angka 121 adalah sebuah palindrom.
Mari kita ambil angka lain, 1242. Jika kita membacanya dari kiri ke kanan, maka angka tersebut adalah 1242 dan jika dibaca dari kanan ke kiri, maka angka tersebut akan terbaca sebagai 2421. Dengan demikian, angka tersebut bukanlah sebuah palindrom.
Kami mengimplementasikan program palindrom dengan membalikkan digit angka dan secara rekursif membandingkan angka yang diberikan dengan representasi terbalik.
Program di bawah ini mengimplementasikan program untuk memeriksa palindrom.
import java.io.*; import java.util.*; public class Main { // periksa apakah num hanya berisi satu digit public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } // fungsi utilitas palindrom public static int isPalindrome_util (int num, int revNum) throws Exception { // kondisi dasar; kembalikan jika num = 0 if (num == 0) { return revNum; } else { //panggilanfungsi utilitas secara rekursif revNum = isPalindrome_util(num / 10, revNum); } // memeriksa apakah digit pertama dari num dan revNum sama if (num % 10 == revNum % 10) { // jika ya, revNum akan berpindah dengan num return revNum / 10; } else { // keluar melempar new Exception(); } } //mengecek apakah bilangan yang diberikan adalah palindrome menggunakan fungsi utilitas palindrome public static int isPalindrome(int num) melemparException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Ya, bilangan yang diberikan " + n + " adalah palindrom."); } catch (Exception e) { System.out.println("Tidak, bilangan yang diberikan " + n + " bukanlah palindrom."); } n = 1221; try { isPalindrome(n);System.out.println("Ya, bilangan yang diberikan " + n + " adalah palindrom."); } catch (Exception e) { System.out.println("Tidak, bilangan yang diberikan " + n + " bukan palindrom."); } } Keluaran
# 3) Membalikkan Rekursi String Java
Diberikan sebuah string "Hello", kita harus membalikkan string tersebut sehingga string yang dihasilkan adalah "olleH".
Hal ini dilakukan dengan menggunakan rekursi. Mulai dari karakter terakhir dalam string, kami secara rekursif mencetak setiap karakter sampai semua karakter dalam string habis.
Program di bawah ini menggunakan rekursi untuk membalikkan string yang diberikan.
class String_Reverse { //metode rekursif untuk membalikkan string yang diberikan void reverseString(String str) { //kondisi dasar; kembalikan jika string bernilai null atau dengan 1 karakter atau kurang if ((str==null)} } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("String yang diberikan: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("String yang dibalikkan: "); obj.reverseString(inputstr); } } Keluaran
#4) Pencarian Biner Rekursi Java
Algoritma pencarian biner adalah algoritma yang terkenal untuk pencarian. Dalam algoritma ini, diberikan sebuah larik terurut dengan n elemen, kita mencari larik ini untuk elemen kunci yang diberikan. Pada awalnya, kita membagi larik menjadi dua bagian dengan menemukan elemen tengah larik.
Kemudian, tergantung pada apakah kunci berada di tengah, kita membatasi pencarian di paruh pertama atau kedua dari larik. Dengan cara ini, proses yang sama diulangi sampai lokasi elemen kunci ditemukan.
Kami akan mengimplementasikan algoritma ini menggunakan rekursi di sini.
import java.util.*; class Binary_Search { // pencarian biner rekursif int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //hitung mid dari array int mid = left + (right - left) / 2; // jika key berada di mid, return mid if (numArray[mid] == key) return mid; // jika key key) return binarySearch(numArray, left, mid - 1, key); // Selanjutnya cari secara rekursif disubarray kanan return binarySearch(numArray, mid + 1, right, key); } // tidak ada elemen dalam array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //mendeklarasikan dan mencetak array int numArray[] = { 4,6,12,16,22}; System.out.println("Array yang diberikan: " + Arrays.toString(numArray)); int len = numArray.length; //panjang arrayint key = 16; //kunci yang akan dicari int hasil = ob.binarySearch(numArray, 0, len - 1, key); if (hasil == -1) System.out.println("Elemen "+ key +" tidak ada"); else System.out.println("Elemen "+ key +" ditemukan di indeks "+ hasil); } } Keluaran
#5) Menemukan Nilai Minimum Dalam Larik Menggunakan Perulangan
Dengan menggunakan rekursi, kita juga dapat menemukan nilai minimum dalam larik.
Program Java untuk menemukan nilai minimum dalam larik diberikan di bawah ini.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //mengembalikan elemen pertama jika hanya satu elemen atau minimum dari elemen array return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray, i + 1, n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Diberikan Array: " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Elemen minimum dari array: " + getMin(numArray, 0, n) + "\n"); } } Keluaran
Ini adalah beberapa contoh dari rekursi. Terlepas dari contoh-contoh ini, banyak masalah lain dalam perangkat lunak yang dapat diimplementasikan dengan menggunakan teknik rekursif.
Jenis Rekursi
Rekursi terdiri dari dua jenis berdasarkan kapan pemanggilan ke metode rekursif.
Benar:
#1) Perulangan Ekor
Ketika pemanggilan ke metode rekursif merupakan pernyataan terakhir yang dieksekusi di dalam metode rekursif, ini disebut "Rekursi Ekor".
Pada rekursi ekor, pernyataan pemanggilan rekursif biasanya dieksekusi bersama dengan pernyataan pengembalian dari metode.
Sintaks umum untuk rekursi ekor diberikan di bawah ini:
methodName (T parameter...){ { if (base_condition == true) { kembalikan hasil; } kembalikan methodName (T parameter...) //ekor rekursi } # 2) Rekursi Kepala
Rekursi kepala adalah pendekatan rekursif apapun yang bukan merupakan rekursi ekor, sehingga rekursi umum pun adalah rekursi ke depan.
Sintaks rekursi kepala adalah sebagai berikut:
methodName (T parameter...){ if (some_condition == true) { return methodName (T parameter...); } return result; } Rekursi Vs Iterasi di Java
| Rekursi | Iterasi |
|---|---|
| Rekursi adalah proses di mana sebuah metode memanggil dirinya sendiri secara berulang-ulang hingga kondisi dasar terpenuhi. | Iterasi adalah proses di mana sepotong kode dieksekusi berulang kali dalam jumlah yang terbatas atau sampai suatu kondisi terpenuhi. |
| Adalah aplikasi untuk fungsi. | Dapat diterapkan untuk loop. |
| Bekerja dengan baik untuk ukuran kode yang lebih kecil. | Bekerja dengan baik untuk ukuran kode yang lebih besar. |
| Memanfaatkan lebih banyak memori karena setiap panggilan rekursif didorong ke stack | Memori yang digunakan relatif lebih sedikit. |
| Sulit untuk men-debug dan memelihara | Lebih mudah untuk men-debug dan memelihara |
| Mengakibatkan stack overflow jika kondisi dasar tidak ditentukan atau tidak tercapai. | Dapat dieksekusi tanpa batas tetapi pada akhirnya akan menghentikan eksekusi dengan kesalahan memori apa pun |
| Kompleksitas waktu sangat tinggi. | Kompleksitas waktu relatif lebih rendah. |
Pertanyaan yang Sering Diajukan
T #1) Bagaimana cara kerja Rekursi di Java?
Jawaban: Dalam rekursi, fungsi rekursif memanggil dirinya sendiri berulang kali hingga kondisi dasar terpenuhi. Memori untuk fungsi yang dipanggil didorong ke tumpukan di bagian atas memori untuk fungsi yang memanggil. Untuk setiap pemanggilan fungsi, salinan variabel lokal dibuat secara terpisah.
Q #2) Mengapa Rekursi digunakan?
Jawaban: Rekursi digunakan untuk memecahkan masalah yang dapat dipecah menjadi masalah yang lebih kecil dan seluruh masalah dapat dinyatakan dalam bentuk masalah yang lebih kecil.
Rekursi juga digunakan untuk masalah-masalah yang terlalu rumit untuk diselesaikan dengan menggunakan pendekatan berulang. Selain itu, masalah-masalah yang kompleksitas waktunya tidak menjadi masalah, gunakanlah rekursi.
Q #3) Apa saja manfaat dari Pengulangan?
Jawaban:
Manfaat dari Recursion meliputi:
- Rekursi mengurangi pemanggilan fungsi yang berlebihan.
- Rekursi memungkinkan kita untuk menyelesaikan masalah dengan mudah jika dibandingkan dengan pendekatan iteratif.
T #4) Mana yang lebih baik - Rekursi atau Iterasi?
Jawaban: Rekursi melakukan pemanggilan berulang kali hingga fungsi dasar tercapai. Dengan demikian, ada overhead memori karena memori untuk setiap pemanggilan fungsi didorong ke stack.
Di sisi lain, iterasi tidak memiliki banyak overhead memori. Eksekusi rekursi lebih lambat daripada pendekatan iteratif. Rekursi mengurangi ukuran kode sementara pendekatan iteratif membuat kode menjadi besar.
Q #5) Apa Keuntungan Rekursi dibandingkan Iterasi?
Jawaban:
- Pengulangan membuat kode menjadi lebih jelas dan singkat.
- Perulangan lebih baik daripada pendekatan iteratif untuk masalah seperti Menara Hanoi, penelusuran pohon, dll.
- Karena setiap pemanggilan fungsi memiliki memori yang didorong ke stack, maka Rekursi menggunakan lebih banyak memori.
- Performa rekursi lebih lambat daripada pendekatan berulang.
Kesimpulan
Rekursi adalah konsep yang sangat penting dalam perangkat lunak terlepas dari bahasa pemrogramannya. Rekursi sebagian besar digunakan untuk memecahkan masalah struktur data seperti menara Hanoi, penjelajahan pohon, daftar bertautan, dll. Meskipun membutuhkan lebih banyak memori, rekursi membuat kode menjadi lebih sederhana dan jelas.
Kita telah menjelajahi semua tentang Rekursi dalam tutorial ini. Kami juga telah menerapkan banyak contoh pemrograman untuk pemahaman yang lebih baik tentang konsep ini.