Kata pengantar
Saya melihat konten ini baru -baru ini ketika saya membaca buku dan saya merasa cukup bermanfaat. Iterasi menggunakan loop (untuk, sementara, lakukan ... Wile) atau iterator, yang keluar saat kondisi loop tidak terpenuhi. Rekursi umumnya merupakan rekursi fungsi, yang dapat dipanggil dengan sendirinya atau dengan panggilan non-langsung, yaitu metode A panggilan metode B, dan metode B panggilan B Metode A pada gilirannya, dan kondisi untuk keluar rekursif adalah pernyataan IF dan yang lain, dan keluar ketika kondisi memenuhi dasar.
Di atas adalah karakteristik sintaks dari iterasi dan rekursi. Apa perbedaan di antara mereka di Java? Mari kita pelajari lebih lanjut tentang artikel ini di bawah ini.
1. Rekursi
Ketika datang ke iterasi, kita harus menyebutkan ekspresi matematika: n!=n*(n-1)*(n-2)*...*1
Ada banyak cara untuk menghitung faktorial. Siapa pun yang memiliki fondasi matematika tertentu tahu n!=n*(n-1)! Oleh karena itu, implementasi kode dapat ditulis secara langsung sebagai:
Kode 1
Int Factorial (int n) {if (n == 1) {return 1; } else {return n*factorial (n-1); }} Saat mengeksekusi kode di atas, mesin sebenarnya perlu melakukan serangkaian perkalian: factorial(n) → factorial(n-1) → factorial(n-2) → ... → factorial(1) . Oleh karena itu, perlu untuk melacak (melacak hasil perhitungan terakhir) dan panggilan multiplikasi untuk melakukan perhitungan (membangun rantai multiplikasi). Jenis operasi yang terus -menerus memanggil itu sendiri disebut rekursi. Rekursi dapat dibagi lebih lanjut menjadi rekursi linier dan rekursi numerik. Jumlah informasi meningkat secara linear dengan input algoritma. Rekursi disebut rekursi linier. Hitung N! (Pabrik) adalah rekursi linier. Karena ketika N meningkat, waktu yang diperlukan untuk perhitungan meningkat secara linear. Jenis informasi lain yang tumbuh secara eksponensial dengan peningkatan input disebut rekursi pohon.
2. Iterasi
Cara lain untuk menghitung N! IS: Pertama Hitung 1 Gandakan dengan 2, kemudian kalikan hasilnya dengan 3, dan kemudian kalikan hasilnya dengan 4 ... dan gandakan sampai N. Selama implementasi program, penghitung dapat ditentukan. Setiap kali perkalian dilakukan, penghitung bertambah sekali sampai nilai penghitung sama dengan N. Kode ini sebagai berikut:
Kode dua
int factorial (int n) {int produk = 1; untuk (int i = 2; i <n; i ++) {Produk *= i; } mengembalikan produk;}Dibandingkan dengan kode satu, kode dua tidak membangun rantai multiplikasi. Saat melakukan setiap langkah perhitungan, Anda hanya perlu mengetahui hasil saat ini (produk) dan nilai -nilai i. Bentuk perhitungan ini disebut iterasi. Ada beberapa kondisi untuk iterasi: 1. Ada variabel dengan nilai awal. 2. Sebuah aturan yang menjelaskan bagaimana nilai variabel diperbarui. 3. Kondisi akhir. (Tiga elemen loop: variabel loop, badan loop dan kondisi penghentian loop). Sama seperti rekursi. Persyaratan waktu yang menjadi linier karena input tumbuh secara linear dapat disebut iterasi linier.
3. Iterasi vs Rekursi
Setelah membandingkan kedua program, kita dapat menemukan bahwa mereka terlihat hampir sama, terutama dalam hal fungsi matematika mereka. Saat menghitung N!, Langkah perhitungan mereka sebanding dengan nilai n. Namun, jika kita mengambil perspektif program dan mempertimbangkan bagaimana mereka berjalan, maka kedua algoritma sangat berbeda.
(Catatan: Teks asli agak tidak relevan tentang perbedaannya, jadi saya tidak akan menerjemahkannya di sini. Berikut ini adalah ringkasan penulis sendiri.)
Pertama -tama, analisis rekursi. Faktanya, hal terbesar tentang rekursi adalah menguraikan algoritma yang kompleks menjadi beberapa langkah berulang yang identik. Oleh karena itu, menggunakan rekursi untuk mengimplementasikan logika komputasi sering kali hanya membutuhkan kode yang sangat singkat untuk dipecahkan, dan kode tersebut lebih mudah dipahami. Namun, rekursi berarti sejumlah besar panggilan fungsi. Alasan mengapa status panggilan fungsi lokal direkam menggunakan tumpukan. Oleh karena itu, ini dapat menyia -nyiakan banyak ruang, dan jika rekursi terlalu dalam, itu dapat menyebabkan tumpukan overflow.
Selanjutnya, analisis iterasi. Bahkan, rekursi dapat digantikan dengan iterasi. Namun, dibandingkan dengan kesederhanaan dan pemahaman rekursi, iterasi lebih kaku dan sulit dipahami. Terutama saat menghadapi skenario yang lebih kompleks. Namun, kesulitan memahami kode juga membawa poin yang lebih jelas. Efisiensi iterasi lebih tinggi dari rekursi dan juga relatif kecil dalam konsumsi ruang.
Harus ada iterasi dalam rekursi, tetapi mungkin tidak ada rekursi dalam iterasi, dan kebanyakan dari mereka dapat dikonversi satu sama lain.
Jika Anda dapat menggunakan iterasi, jangan gunakan rekursi. Fungsi panggilan secara rekursif tidak hanya membuang -buang ruang, tetapi juga dapat dengan mudah menyebabkan tumpukan overflow jika rekursi terlalu dalam.
4. Rekursi Angka
Seperti yang disebutkan sebelumnya, jumlah informasi yang meningkat secara rekursif pohon secara eksponensial dengan peningkatan input. Urutan Fibonacci adalah contoh khas:
Dalam deskripsi teks, jumlah dari dua angka pertama dalam urutan fibonacci sama dengan angka ketiga: 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
Kode implementasi rekursif adalah sebagai berikut:
int fib (int n) {if (n == 0) {return 0; } lain jika (n == 1) {return 1; } else {return fib (n-1) + fib (n-2); }} Selama proses perhitungan, untuk menghitung fib(5) , program harus terlebih dahulu menghitung fib(4) dan fib(3) . Untuk menghitung fib(4) , program ini juga perlu menghitung fib(3) dan fib(2) pertama. FIB (3) dihitung dua kali selama proses ini.
Dari proses perhitungan yang dianalisis di atas, kita dapat menarik kesimpulan: ada perhitungan redundan untuk mengimplementasikan urutan fibonacci menggunakan rekursi.
Seperti disebutkan di atas, algoritma rekursif umumnya dapat diimplementasikan secara iteratif, dan hal yang sama berlaku untuk perhitungan urutan fibonacci.
int fib (int n) {int fib = 0; int a = 1; untuk (int i = 0; i <n; i ++) {int temp = fib; fib = fib + a; a = temp; } return fib;}Meskipun akan ada perhitungan yang berlebihan dalam metode rekursi, itu dapat digantikan dengan iterasi. Tetapi ini tidak berarti bahwa rekursi dapat sepenuhnya diganti. Karena rekursi memiliki keterbacaan yang lebih baik.
Meringkaskan
Di atas adalah seluruh konten artikel ini. Saya berharap konten artikel ini akan membantu semua orang dalam belajar atau menggunakan Java. Jika Anda memiliki pertanyaan, Anda dapat meninggalkan pesan untuk berkomunikasi.