Apakah benar untuk mengatakan bahwa di mana pun rekursi digunakan, sebuah forloop dapat digunakan? Dan jika rekursi biasanya lebih lambat, apa alasan teknis untuk menggunakannya forberulang kali?

Dan jika selalu memungkinkan untuk mengubah rekursi menjadi forloop, apakah ada aturan praktis untuk melakukannya?

Rekursi biasanya jauh lebih lambat karena semua panggilan fungsi harus disimpan dalam tumpukan untuk memungkinkan kembali ke fungsi pemanggil. Dalam banyak kasus, memori harus dialokasikan dan disalin untuk mengimplementasikan isolasi cakupan.

Beberapa pengoptimalan, seperti pengoptimalan panggilan ekor , membuat rekursi lebih cepat tetapi tidak selalu memungkinkan, dan tidak diterapkan dalam semua bahasa.

Alasan utama untuk menggunakan rekursi adalah

• yang lebih intuitif dalam banyak kasus saat meniru pendekatan kita terhadap masalah
• bahwa beberapa struktur data seperti pohon lebih mudah untuk dijelajahi menggunakan rekursi (atau akan membutuhkan tumpukan dalam hal apapun)

Tentu saja setiap rekursi dapat dimodelkan sebagai semacam loop: itulah yang pada akhirnya akan dilakukan oleh CPU. Dan rekursi itu sendiri, secara lebih langsung, berarti menempatkan pemanggilan fungsi dan cakupan dalam tumpukan. Tetapi mengubah algoritme rekursif Anda menjadi perulangan mungkin memerlukan banyak pekerjaan dan membuat kode Anda kurang dapat dipelihara: seperti untuk setiap pengoptimalan, itu hanya boleh dicoba ketika beberapa profil atau bukti menunjukkan itu diperlukan.

Apakah benar untuk mengatakan bahwa di mana pun rekursi digunakan, loop for dapat digunakan?

Ya, karena rekursi di sebagian besar CPU dimodelkan dengan loop dan struktur data tumpukan.

Dan jika rekursi biasanya lebih lambat, apa alasan teknis untuk menggunakannya?

Ini tidak "biasanya lebih lambat": itu rekursi yang diterapkan secara tidak benar yang lebih lambat. Selain itu, kompiler modern pandai mengubah beberapa rekursi menjadi loop bahkan tanpa bertanya.

Dan jika selalu memungkinkan untuk mengubah rekursi menjadi loop for, apakah ada aturan praktis untuk melakukannya?

Tulis program iteratif untuk algoritme yang paling dipahami saat dijelaskan secara berulang; tulis program rekursif untuk algoritme yang paling baik dijelaskan secara rekursif.

Misalnya, mencari pohon biner, menjalankan quicksort, dan ekspresi parsing dalam banyak bahasa pemrograman sering dijelaskan secara rekursif. Ini juga paling baik dikodekan secara rekursif. Di sisi lain, menghitung faktorial dan menghitung angka Fibonacci jauh lebih mudah dijelaskan dalam hal iterasi. Menggunakan rekursi untuk mereka seperti menampar lalat dengan palu godam: itu bukan ide yang baik, bahkan ketika palu godam melakukan pekerjaan yang sangat bagus ⁺ .

Pertanyaan :

Dan jika rekursi biasanya lebih lambat apa alasan teknis untuk menggunakannya selama iterasi loop?

Jawaban:

Karena pada beberapa algoritma sulit untuk menyelesaikannya secara iteratif. Cobalah untuk memecahkan pencarian kedalaman-pertama secara rekursif dan iteratif. Anda akan mendapatkan gagasan bahwa sulit untuk menyelesaikan DFS dengan iterasi.

Hal baik lainnya untuk dicoba: Cobalah untuk menulis Merge sort secara iteratif. Ini akan memakan waktu cukup lama.

Pertanyaan :

Apakah benar untuk mengatakan bahwa di mana pun rekursi digunakan, loop for dapat digunakan?

Jawaban:

Iya. Utas ini memiliki jawaban yang sangat bagus untuk ini.

Pertanyaan :

Dan jika selalu memungkinkan untuk mengubah rekursi menjadi loop for, apakah ada aturan praktis untuk melakukannya?

Jawaban:

Percayalah kepadaku. Cobalah untuk menulis versi Anda sendiri untuk menyelesaikan pencarian kedalaman-pertama secara berulang. Anda akan melihat bahwa beberapa masalah lebih mudah diselesaikan secara rekursif.

Petunjuk: Rekursi bagus saat Anda memecahkan masalah yang dapat diselesaikan dengan teknik bagi dan taklukkan .

Selain lebih lambat, rekursi juga dapat mengakibatkan kesalahan stack overflow tergantung seberapa dalam prosesnya.

Untuk menulis metode yang setara menggunakan iterasi, kita harus secara eksplisit menggunakan tumpukan. Fakta bahwa versi iteratif memerlukan tumpukan untuk solusinya menunjukkan bahwa masalahnya cukup sulit sehingga dapat diuntungkan dari rekursi. Sebagai aturan umum, rekursi paling cocok untuk masalah yang tidak dapat diselesaikan dengan jumlah memori tetap dan akibatnya memerlukan tumpukan saat diselesaikan secara berulang. Karena itu, rekursi dan iterasi dapat menunjukkan hasil yang sama sementara mereka mengikuti pola yang berbeda. Untuk memutuskan metode mana yang bekerja lebih baik adalah kasus per kasus dan praktik terbaik adalah memilih berdasarkan pola yang diikuti oleh masalah.

Misalnya, untuk mencari bilangan segitiga ke-n dari barisan Segitiga: 1 3 6 10 15… Program yang menggunakan algoritma iteratif untuk mencari bilangan segitiga ke-n:

Menggunakan algoritma iteratif:

//Triangular.java
import java.util.*;
class Triangular {
   public static int iterativeTriangular(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i ++)
         sum += i;
      return sum;
   }
   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                            iterativeTriangular(n));
   }
}//enter code here

Menggunakan algoritma rekursif:

//Triangular.java
import java.util.*;
class Triangular {
   public static int recursiveTriangular(int n) {
      if (n == 1)
     return 1;  
      return recursiveTriangular(n-1) + n; 
   }

   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                             recursiveTriangular(n)); 
   }
}

Sebagian besar jawaban tampaknya berasumsi bahwa iterative= for loop. Jika perulangan for Anda tidak dibatasi ( a la C, Anda dapat melakukan apa pun yang Anda inginkan dengan penghitung perulangan Anda), maka itu benar. Jika ini adalah loop nyata for (katakanlah seperti di Python atau sebagian besar bahasa fungsional di mana Anda tidak dapat memodifikasi penghitung loop secara manual), maka itu tidak benar.

Semua fungsi (dapat dihitung) dapat diimplementasikan baik secara rekursif dan menggunakan whileloop (atau lompatan bersyarat, yang pada dasarnya adalah hal yang sama). Jika Anda benar-benar membatasi diri for loopsAnda, Anda hanya akan mendapatkan subset dari fungsi-fungsi tersebut (yang rekursif primitif, jika operasi dasar Anda masuk akal). Memang, ini adalah subset yang cukup besar yang kebetulan berisi setiap fungsi yang cenderung Anda encouter dalam praktiknya.

Yang jauh lebih penting adalah banyak fungsi yang sangat mudah diimplementasikan secara rekursif dan sangat sulit untuk diterapkan secara iteratif (mengelola tumpukan panggilan Anda secara manual tidak dihitung).

Ya, seperti yang dikatakan oleh Thanakron Tandavas ,

Rekursi bagus saat Anda memecahkan masalah yang dapat diselesaikan dengan teknik bagi dan taklukkan.

Misalnya: Menara Hanoi

1. N cincin dalam ukuran yang semakin besar
2. 3 tiang
3. Cincin mulai ditumpuk di tiang 1. Tujuannya adalah untuk memindahkan cincin agar bertumpuk di tiang 3 ... Tapi
   • Hanya bisa menggerakkan satu dering dalam satu waktu.
   • Tidak bisa meletakkan cincin yang lebih besar di atas yang lebih kecil.
4. Solusi berulang adalah "kuat namun jelek"; solusi rekursif adalah "elegan".

Sepertinya saya ingat profesor ilmu komputer saya mengatakan kembali pada hari itu bahwa semua masalah yang memiliki solusi rekursif juga memiliki solusi berulang. Dia mengatakan bahwa solusi rekursif biasanya lebih lambat, tetapi sering digunakan ketika lebih mudah untuk bernalar dan kode daripada solusi berulang.

Namun, dalam kasus solusi rekursif yang lebih maju, saya tidak percaya bahwa itu akan selalu dapat menerapkannya menggunakan forloop sederhana .

rekursi + menghafal dapat menghasilkan solusi yang lebih efisien dibandingkan dengan pendekatan iteratif murni, misalnya periksa ini: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

Jawaban singkatnya: trade off adalah rekursi lebih cepat dan untuk loop memakan lebih sedikit memori di hampir semua kasus. Namun biasanya ada cara untuk mengubah loop atau rekursi agar berjalan lebih cepat