Rekursi Di Jawa

1. Perkenalan

Pada artikel ini, kami akan fokus pada konsep inti dalam bahasa pemrograman apa pun - rekursi.

Kami akan menjelaskan karakteristik fungsi rekursif dan menunjukkan bagaimana menggunakan rekursi untuk menyelesaikan berbagai masalah di Java.

2. Pahami Rekursi

2.1. Definisi

Di Java, mekanisme pemanggilan fungsi mendukung kemungkinan memiliki pemanggilan metode itu sendiri . Fungsionalitas ini dikenal sebagai rekursi .

Misalnya, kita ingin menjumlahkan bilangan bulat dari 0 ke beberapa nilai n :

public int sum(int n) { if (n >= 1) { return sum(n - 1) + n; } return n; }

Ada dua persyaratan utama dari fungsi rekursif:

  • Kondisi Berhenti - fungsi mengembalikan nilai ketika kondisi tertentu terpenuhi, tanpa panggilan rekursif lebih lanjut
  • Panggilan Rekursif - fungsi memanggil dirinya sendiri dengan input yang selangkah lebih dekat ke kondisi berhenti

Setiap panggilan rekursif akan menambahkan bingkai baru ke memori tumpukan JVM. Jadi, jika kita tidak memperhatikan seberapa dalam panggilan rekursif kita bisa menyelam, pengecualian kehabisan memori dapat terjadi.

Masalah potensial ini dapat dicegah dengan memanfaatkan pengoptimalan rekursi ekor.

2.2. Rekursi Ekor versus Rekursi Kepala

Kami merujuk ke fungsi rekursif sebagai rekursi-ekor ketika panggilan rekursif adalah hal terakhir yang dijalankan oleh fungsi. Jika tidak, ini dikenal sebagai rekursi kepala .

Implementasi kita di atas fungsi sum () adalah contoh rekursi head dan dapat diubah menjadi rekursi ekor:

public int tailSum(int currentSum, int n) { if (n <= 1) { return currentSum + n; } return tailSum(currentSum + n, n - 1); }

Dengan rekursi ekor, panggilan rekursif adalah hal terakhir yang dilakukan metode, jadi tidak ada yang tersisa untuk dieksekusi dalam fungsi saat ini.

Jadi, secara logis tidak perlu menyimpan bingkai tumpukan fungsi saat ini.

Meskipun kompilator dapat memanfaatkan titik ini untuk mengoptimalkan memori, perlu dicatat bahwa kompilator Java tidak mengoptimalkan rekursi tail untuk saat ini .

2.3. Rekursi versus Iterasi

Rekursi dapat membantu menyederhanakan implementasi beberapa masalah rumit dengan membuat kode lebih jelas dan lebih mudah dibaca.

Tetapi seperti yang telah kita lihat, pendekatan rekursif sering kali membutuhkan lebih banyak memori karena memori tumpukan yang dibutuhkan meningkat dengan setiap panggilan rekursif.

Sebagai alternatif, jika kita bisa menyelesaikan masalah dengan rekursi, kita juga bisa menyelesaikannya dengan iterasi.

Misalnya, metode penjumlahan kami dapat diimplementasikan menggunakan iterasi:

public int iterativeSum(int n) { int sum = 0; if(n < 0) { return -1; } for(int i=0; i<=n; i++) { sum += i; } return sum; }

Dibandingkan dengan rekursi, pendekatan iteratif berpotensi memberikan kinerja yang lebih baik. Dengan demikian, iterasi akan lebih rumit dan lebih sulit dipahami dibandingkan dengan rekursi, misalnya: melintasi pohon biner.

Membuat pilihan yang tepat antara rekursi head, rekursi ekor dan pendekatan berulang semuanya bergantung pada masalah dan situasi spesifik.

3. Contoh

Sekarang, mari kita coba menyelesaikan beberapa masalah dengan cara rekursif.

3.1. Menemukan Kekuatan Sepuluh N-Th

Misalkan kita perlu menghitung pangkat ke- n dari 10. Di sini input kita adalah n. Berpikir secara rekursif, kita dapat menghitung (n-1) pangkat 10 terlebih dahulu, dan mengalikan hasilnya dengan 10.

Kemudian, untuk menghitung pangkat ke- (n-1) dari 10 akan menjadi pangkat ke- (n-2) dari 10 dan mengalikan hasilnya dengan 10, dan seterusnya. Kita akan terus seperti ini sampai kita mencapai titik di mana kita perlu menghitung pangkat (nn) ke-10, yaitu 1.

Jika kami ingin menerapkan ini di Java, kami akan menulis:

public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10; }

3.2. Menemukan Elemen ke-N dari Deret Fibonacci

Dimulai dengan 0 dan 1 , yang Fibonacci urutan adalah urutan angka di mana setiap nomor didefinisikan sebagai jumlah dari dua angka melanjutkan itu : 0 1 1 2 3 5 8 13 21 34 55 ...

Jadi, diberi angka n , masalah kita adalah mencari elemen ke- n dari Urutan Fibonacci . Untuk mengimplementasikan solusi rekursif, kita perlu mencari tahu Kondisi Berhenti dan Panggilan Rekursif .

Untungnya, ini sangat mudah.

Mari kita sebut f (n) nilai ke- n dari urutan tersebut. Kemudian kita akan memiliki f (n) = f (n-1) + f (n-2) ( Panggilan Rekursif ) .

Sedangkan f (0) = 0 dan f (1) = 1 ( Stop Condition) .

Kemudian, sangat jelas bagi kami untuk menentukan metode rekursif untuk menyelesaikan masalah:

public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

3.3. Mengonversi dari Desimal ke Biner

Sekarang, mari kita pertimbangkan masalah mengubah angka desimal menjadi biner. Persyaratannya adalah untuk menerapkan metode yang menerima nilai bilangan bulat positif n dan mengembalikan representasi String biner .

Salah satu pendekatan untuk mengonversi bilangan desimal menjadi biner adalah dengan membagi nilainya dengan 2, catat sisanya dan lanjutkan membagi hasil bagi dengan 2.

Kami terus membagi seperti itu sampai kami mendapatkan hasil bagi 0 . Kemudian, dengan menuliskan semua sisa dalam urutan cadangan, kita mendapatkan string biner.

Karenanya, masalah kita adalah menulis metode yang mengembalikan sisa-sisa ini dalam urutan cadangan:

public String toBinary(int n) { if (n <= 1 ) { return String.valueOf(n); } return toBinary(n / 2) + String.valueOf(n % 2); }

3.4. Ketinggian Pohon Biner

Tinggi pohon biner didefinisikan sebagai jumlah tepi dari akar hingga daun terdalam. Masalah kita sekarang adalah menghitung nilai ini untuk pohon biner tertentu.

Salah satu pendekatan sederhana adalah menemukan daun terdalam kemudian menghitung tepi antara akar dan daun itu.

Tetapi mencoba memikirkan solusi rekursif, kita dapat menyatakan kembali definisi tinggi pohon biner sebagai tinggi maksimal dari cabang kiri akar dan cabang kanan akar, ditambah 1 .

Jika akar tidak memiliki cabang kiri dan kanan, tingginya nol .

Inilah implementasi kami:

public int calculateTreeHeight(BinaryNode root){ if (root!= null) { if (root.getLeft() != null || root.getRight() != null) { return 1 + max(calculateTreeHeight(root.left), calculateTreeHeight(root.right)); } } return 0; }

Oleh karena itu, kami melihat bahwa beberapa masalah dapat diselesaikan dengan rekursi dengan cara yang sangat sederhana.

4. Kesimpulan

Dalam tutorial ini, kami telah memperkenalkan konsep rekursi di Java dan mendemonstrasikannya dengan beberapa contoh sederhana.

Penerapan artikel ini dapat ditemukan di Github.