Apakah rekursi lebih cepat daripada perulangan?

Saya tahu bahwa rekursi kadang-kadang jauh lebih bersih daripada perulangan, dan saya tidak bertanya apa-apa tentang kapan saya harus menggunakan rekursi atas iterasi, saya tahu sudah banyak pertanyaan tentang itu.

Apa yang saya minta adalah, adalah rekursi pernah lebih cepat dari lingkaran? Bagi saya sepertinya, Anda akan selalu dapat memperbaiki loop dan membuatnya bekerja lebih cepat daripada fungsi rekursif karena loop tidak ada terus-menerus mengatur frame stack baru.

Saya secara khusus mencari apakah rekursi lebih cepat dalam aplikasi di mana rekursi adalah cara yang tepat untuk menangani data, seperti dalam beberapa fungsi penyortiran, dalam pohon biner, dll.

Ini tergantung pada bahasa yang digunakan. Anda menulis 'agnostik bahasa', jadi saya akan memberikan beberapa contoh.

Di Jawa, C, dan Python, rekursi cukup mahal dibandingkan dengan iterasi (secara umum) karena membutuhkan alokasi bingkai tumpukan baru. Dalam beberapa kompiler C, seseorang dapat menggunakan flag compiler untuk menghilangkan overhead ini, yang mengubah jenis rekursi tertentu (sebenarnya, jenis panggilan ekor tertentu) menjadi lompatan alih-alih panggilan fungsi.

Dalam implementasi bahasa pemrograman fungsional, kadang-kadang, iterasi bisa sangat mahal dan rekursi bisa sangat murah. Dalam banyak hal, rekursi diubah menjadi lompatan sederhana, tetapi mengubah variabel loop (yang bisa berubah-ubah) kadang - kadang membutuhkan beberapa operasi yang relatif berat, terutama pada implementasi yang mendukung banyak utas eksekusi. Mutasi mahal di beberapa lingkungan ini karena interaksi antara mutator dan pengumpul sampah, jika keduanya berjalan pada saat yang sama.

Saya tahu bahwa dalam beberapa implementasi Skema, rekursi umumnya akan lebih cepat daripada perulangan.

Singkatnya, jawabannya tergantung pada kode dan implementasinya. Gunakan gaya apa pun yang Anda inginkan. Jika Anda menggunakan bahasa fungsional, rekursi mungkin lebih cepat. Jika Anda menggunakan bahasa imperatif, iterasi mungkin lebih cepat. Di beberapa lingkungan, kedua metode akan menghasilkan perakitan yang sama yang dihasilkan (taruh itu di pipa Anda dan asap itu).

Tambahan: Dalam beberapa lingkungan, alternatif terbaik bukanlah rekursi atau iterasi melainkan fungsi urutan yang lebih tinggi. Ini termasuk "peta", "filter", dan "kurangi" (yang juga disebut "lipatan"). Tidak hanya ini gaya yang disukai, tidak hanya mereka sering lebih bersih, tetapi di beberapa lingkungan fungsi-fungsi ini adalah yang pertama (atau hanya) untuk mendapatkan dorongan dari paralelisasi otomatis - sehingga mereka dapat secara signifikan lebih cepat daripada iterasi atau rekursi. Data Parallel Haskell adalah contoh dari lingkungan seperti itu.

Pemahaman daftar adalah alternatif lain, tetapi ini biasanya hanya gula sintaksis untuk iterasi, rekursi, atau fungsi tingkat tinggi.

Apakah rekursi lebih cepat dari satu loop?

Tidak, Iterasi akan selalu lebih cepat daripada Rekursi. (dalam Arsitektur Von Neumann)

Penjelasan:

Jika Anda membangun operasi minimum komputer generik dari awal, "Iterasi" diutamakan sebagai blok penyusun dan lebih sedikit sumber daya daripada "rekursi", ergo lebih cepat.

Membangun mesin pseudo-komputasi dari awal:

Tanyai diri Anda : Apa yang Anda perlukan untuk menghitung suatu nilai, yaitu mengikuti algoritma dan mencapai hasil?

Kami akan membangun hierarki konsep, mulai dari awal dan mendefinisikan di tempat pertama konsep dasar, inti, kemudian membangun konsep tingkat kedua dengan itu, dan seterusnya.

1. Konsep Pertama: Sel memori, penyimpanan, Status . Untuk melakukan sesuatu, Anda perlu tempat untuk menyimpan nilai hasil akhir dan menengah. Mari kita asumsikan kita memiliki array tak terbatas dari sel "integer", yang disebut Memory , M [0..Infinite].

2. Instruksi: melakukan sesuatu - mengubah sel, mengubah nilainya. ubah status . Setiap instruksi menarik melakukan transformasi. Instruksi dasar adalah:

   a) Atur & pindahkan sel memori

   • menyimpan nilai ke dalam memori, misalnya: store 5 m [4]
   • salin nilai ke posisi lain: mis .: store m [4] m [8]

   b) Logika dan aritmatika

   • dan, atau, xor, tidak
   • tambahkan, sub, mul, div. mis. tambahkan m [7] m [8]

3. An Executing Agent : inti dalam CPU modern. "Agen" adalah sesuatu yang dapat menjalankan instruksi. Sebuah Agen juga bisa menjadi orang yang mengikuti algoritma di atas kertas.

4. Urutan langkah-langkah: urutan instruksi : yaitu: lakukan ini dulu, lakukan ini setelah, dll. Urutan instruksi yang penting. Bahkan satu kalimat ekspresi adalah "urutan instruksi imperatif". Jika Anda memiliki ekspresi dengan "urutan evaluasi" tertentu maka Anda memiliki langkah - langkah . Itu berarti daripada bahkan satu ekspresi yang dikomposisikan memiliki "langkah" dan juga memiliki variabel lokal implisit (sebut saja "hasil"). misalnya:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   Ekspresi di atas menyiratkan 3 langkah dengan variabel "hasil" implisit.

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   Jadi bahkan ekspresi infiks, karena Anda memiliki urutan evaluasi tertentu, adalah urutan instruksi yang penting . Ekspresi menyiratkan urutan operasi yang akan dibuat dalam urutan tertentu, dan karena ada langkah - langkah , ada juga variabel perantara "hasil" implisit.

5. Pointer Instruksi : Jika Anda memiliki urutan langkah-langkah, Anda juga memiliki "pointer instruksi" implisit. Penunjuk instruksi menandai instruksi selanjutnya, dan maju setelah instruksi dibaca tetapi sebelum instruksi dieksekusi.

   Dalam pseudo-computing-machine ini, Instruction Pointer adalah bagian dari Memory . (Catatan: Biasanya Instruction Pointer akan menjadi "register khusus" dalam inti CPU, tetapi di sini kami akan menyederhanakan konsep dan menganggap semua data (termasuk register) adalah bagian dari "Memori")

6. Langsung - Setelah Anda memiliki jumlah langkah yang dipesan dan Instruksi Pointer , Anda dapat menerapkan instruksi " store " untuk mengubah nilai Pointer Instruksi itu sendiri. Kami akan menyebut penggunaan spesifik dari instruksi toko ini dengan nama baru: Jump . Kami menggunakan nama baru karena lebih mudah untuk memikirkannya sebagai konsep baru. Dengan mengubah pointer instruksi, kami menginstruksikan agen untuk "pergi ke langkah x".

7. Iterasi Infinite : Dengan melompat mundur, sekarang Anda dapat membuat agen "mengulang" sejumlah langkah tertentu. Pada titik ini kita memiliki Iterasi tanpa batas.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. Bersyarat - Eksekusi instruksi bersyarat. Dengan klausa "kondisional", Anda dapat menjalankan salah satu dari beberapa instruksi berdasarkan kondisi saat ini (yang dapat diatur dengan instruksi sebelumnya).

9. Iterasi yang Tepat : Sekarang dengan klausa kondisional , kita dapat menghindari loop tak terbatas dari instruksi lompat kembali . Kami sekarang memiliki loop kondisional dan kemudian Iterasi yang tepat

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  // jump only if the previous 
                           // sub instruction did not result in 0
   
   // this loop will be repeated 1000 times
   // here we have proper ***iteration***, a conditional loop.
   

10. Penamaan : memberi nama ke lokasi memori tertentu yang menyimpan data atau menahan langkah . Ini hanya "kemudahan" untuk dimiliki. Kami tidak menambahkan instruksi baru dengan memiliki kapasitas untuk mendefinisikan "nama" untuk lokasi memori. "Penamaan" bukan instruksi untuk agen, itu hanya kenyamanan bagi kami. Penamaan membuat kode (pada titik ini) lebih mudah dibaca dan lebih mudah diubah.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    

11. Subrutin satu tingkat : Misalkan ada serangkaian langkah yang perlu Anda lakukan sesering mungkin. Anda dapat menyimpan langkah-langkah dalam posisi yang disebutkan dalam memori dan kemudian melompat ke posisi itu ketika Anda perlu menjalankannya (panggilan). Pada akhir urutan Anda harus kembali ke titik panggilan untuk melanjutkan eksekusi. Dengan mekanisme ini, Anda membuat instruksi baru (subrutin) dengan menyusun instruksi inti.

    Implementasi: (tidak diperlukan konsep baru)

    • Simpan Instruction Pointer saat ini dalam posisi memori yang telah ditentukan
    • lompat ke subrutin
    • di akhir subrutin, Anda mengambil Instruksi Pointer dari lokasi memori yang telah ditentukan, secara efektif melompat kembali ke instruksi berikut dari panggilan asli

    Masalah dengan implementasi satu tingkat : Anda tidak dapat memanggil subrutin lain dari subrutin. Jika ya, Anda akan menimpa alamat yang kembali (variabel global), jadi Anda tidak bisa membuat panggilan.

    Untuk memiliki Implementasi yang lebih baik untuk subrutin: Anda memerlukan STACK

12. Stack : Anda mendefinisikan ruang memori untuk berfungsi sebagai "tumpukan", Anda dapat "mendorong" nilai-nilai pada tumpukan, dan juga "pop" nilai "dorongan" terakhir. Untuk mengimplementasikan stack, Anda memerlukan Stack Pointer (mirip dengan Instruction Pointer) yang menunjuk ke "head" sebenarnya dari stack. Ketika Anda "mendorong" suatu nilai, penumpukan tumpukan akan berkurang dan Anda menyimpan nilainya. Ketika Anda "pop", Anda mendapatkan nilai di Stack Pointer yang sebenarnya dan kemudian Stack Pointer bertambah.

13. Subrutin Sekarang kami memiliki tumpukan, kami dapat menerapkan subrutin yang tepat yang memungkinkan panggilan bersarang . Implementasinya mirip, tetapi alih-alih menyimpan Instruction Pointer dalam posisi memori yang telah ditentukan, kami "mendorong" nilai IP dalam tumpukan . Pada akhir subrutin, kami hanya "pop" nilai dari tumpukan, secara efektif melompat kembali ke instruksi setelah panggilan asli . Implementasi ini, memiliki "tumpukan" memungkinkan memanggil subrutin dari subrutin lain. Dengan implementasi ini kita dapat membuat beberapa level abstraksi ketika mendefinisikan instruksi baru sebagai subrutin, dengan menggunakan instruksi inti atau subrutin lainnya sebagai blok bangunan.

14. Rekursi : Apa yang terjadi ketika subrutin memanggil dirinya sendiri? Ini disebut "rekursi".

    Masalah: Menimpa hasil perantara lokal yang dapat disimpan oleh subrutin dalam memori. Karena Anda memanggil / menggunakan kembali langkah-langkah yang sama, jika hasil antara disimpan di lokasi memori yang telah ditentukan (variabel global) mereka akan ditimpa pada panggilan bersarang.

    Solusi: Untuk memungkinkan rekursi, subrutin harus menyimpan hasil antara lokal di stack , oleh karena itu, pada setiap panggilan rekursif (langsung atau tidak langsung) hasil antara disimpan di lokasi memori yang berbeda.

...

Setelah mencapai rekursi kita berhenti di sini.

Kesimpulan:

Dalam Arsitektur Von Neumann, jelas "Iterasi" adalah konsep yang lebih sederhana / dasar daripada "Rekursi" . Kami memiliki bentuk "Iterasi" di level 7, sedangkan "Rekursi" berada pada level 14 dari hirarki konsep.

Iterasi akan selalu lebih cepat dalam kode mesin karena itu menyiratkan lebih sedikit instruksi sehingga siklus CPU lebih sedikit.

Mana yang lebih baik"?

• Anda harus menggunakan "iterasi" ketika Anda sedang memproses struktur data sederhana dan berurutan, dan di mana-mana "loop sederhana" akan dilakukan.

• Anda harus menggunakan "rekursi" ketika Anda perlu memproses struktur data rekursif (saya suka menyebutnya "Struktur Data Fraktal"), atau ketika solusi rekursif jelas lebih "elegan".

Saran : gunakan alat terbaik untuk pekerjaan itu, tetapi pahami cara kerja dalam setiap alat untuk memilih dengan bijak.

Akhirnya, perhatikan bahwa Anda memiliki banyak kesempatan untuk menggunakan rekursi. Anda memiliki Struktur Data Rekursif di mana-mana, Anda sedang melihatnya sekarang: bagian DOM yang mendukung apa yang Anda baca adalah RDS, ekspresi JSON adalah RDS, sistem file hierarkis di komputer Anda adalah RDS, yaitu: Anda memiliki direktori root, yang berisi file dan direktori, setiap direktori yang berisi file dan direktori, setiap direktori yang berisi file dan direktori ...

Rekursi mungkin lebih cepat di mana alternatifnya adalah mengelola tumpukan secara eksplisit, seperti dalam algoritma penyortiran atau pohon biner yang Anda sebutkan.

Saya punya kasus di mana menulis ulang algoritma rekursif di Jawa membuatnya lebih lambat.

Jadi pendekatan yang tepat adalah pertama-tama menulisnya dengan cara yang paling alami, hanya mengoptimalkan jika profil menunjukkan itu penting, dan kemudian mengukur perbaikan yang seharusnya.

Rekursi ekor secepat perulangan. Banyak bahasa fungsional menerapkan rekursi ekor di dalamnya.

Pertimbangkan apa yang mutlak harus dilakukan untuk masing-masing, iterasi dan rekursi.

• iterasi: lompatan ke awal lingkaran
• rekursi: lompatan ke awal fungsi yang disebut

Anda melihat bahwa tidak ada banyak ruang untuk perbedaan di sini.

(Saya menganggap rekursi menjadi tail-call dan kompiler menyadari optimasi itu).

Sebagian besar jawaban di sini melupakan penyebab jelas mengapa rekursi seringkali lebih lambat daripada solusi berulang. Ini terkait dengan penumpukan dan penumpukan bingkai tumpukan tetapi tidak persis seperti itu. Ini umumnya perbedaan besar dalam penyimpanan variabel otomatis untuk setiap rekursi. Dalam algoritma berulang dengan loop, variabel sering disimpan dalam register dan bahkan jika mereka tumpah, mereka akan berada di cache Level 1. Dalam algoritma rekursif, semua status perantara dari variabel disimpan di stack, artinya mereka akan menimbulkan lebih banyak tumpahan ke memori. Ini berarti bahwa bahkan jika ia membuat jumlah operasi yang sama, ia akan memiliki banyak memori yang diakses di loop panas dan apa yang membuatnya lebih buruk, operasi memori ini memiliki tingkat penggunaan kembali yang buruk membuat cache kurang efektif.

Algoritma rekursif TL; DR umumnya memiliki perilaku cache yang lebih buruk daripada yang berulang.

Sebagian besar jawaban di sini salah . Jawaban yang tepat adalah itu tergantung . Sebagai contoh, berikut adalah dua fungsi C yang berjalan melalui pohon. Pertama yang rekursif:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

Dan di sini adalah fungsi yang sama diimplementasikan menggunakan iterasi:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

Tidak penting untuk memahami detail kode. Hanya itu psimpul dan yang P_FOR_EACH_CHILDberjalan. Dalam versi iteratif kita perlu tumpukan eksplisit stke mana node didorong dan kemudian muncul dan dimanipulasi.

Fungsi rekursif berjalan jauh lebih cepat daripada yang iteratif. Alasannya adalah karena dalam yang terakhir, untuk setiap item, a CALLke fungsi st_pushdiperlukan dan kemudian ke lain st_pop.

Di yang pertama, Anda hanya memiliki rekursif CALLuntuk setiap node.

Plus, mengakses variabel di callstack sangat cepat. Ini berarti Anda membaca dari memori yang cenderung selalu berada di cache terdalam. Tumpukan eksplisit, di sisi lain, harus didukung oleh malloc: ed memori dari heap yang jauh lebih lambat untuk diakses.

Dengan optimasi yang cermat, seperti inlining st_pushdan st_pop, saya dapat mencapai kesetaraan dengan pendekatan rekursif. Tapi setidaknya di komputer saya, biaya mengakses memori tumpukan lebih besar daripada biaya panggilan rekursif.

Tapi diskusi ini adalah sebagian besar diperdebatkan karena rekursif pohon berjalan adalah tidak benar . Jika Anda memiliki pohon yang cukup besar, Anda akan kehabisan ruang callstack yang mengapa algoritma iteratif harus digunakan.

Secara umum, tidak, rekursi tidak akan lebih cepat dari satu loop dalam penggunaan realistis yang memiliki implementasi yang layak di kedua bentuk. Maksud saya, tentu saja, Anda dapat membuat kode loop yang membutuhkan waktu lama, tetapi akan ada cara yang lebih baik untuk mengimplementasikan loop yang sama yang dapat mengungguli setiap implementasi dari masalah yang sama melalui rekursi.

Anda memukul paku di kepala tentang alasannya; membuat dan menghancurkan bingkai tumpukan lebih mahal daripada lompatan sederhana.

Namun, harap dicatat bahwa saya berkata "memiliki implementasi yang layak dalam kedua bentuk". Untuk hal-hal seperti banyak algoritma penyortiran, cenderung tidak ada cara yang sangat layak untuk mengimplementasikannya yang tidak secara efektif mengatur versi stack-nya sendiri, karena pemijahan "tugas" anak yang merupakan bagian dari proses. Jadi, rekursi mungkin sama cepatnya dengan mencoba mengimplementasikan algoritma melalui perulangan.

Sunting: Jawaban ini mengasumsikan bahasa non-fungsional, di mana sebagian besar tipe data dasar bisa berubah. Itu tidak berlaku untuk bahasa fungsional.

Dalam sistem realistis apa pun, tidak, membuat bingkai tumpukan akan selalu lebih mahal daripada INC dan JMP. Itu sebabnya kompiler yang sangat bagus secara otomatis mengubah rekursi ekor menjadi panggilan ke frame yang sama, yaitu tanpa overhead, sehingga Anda mendapatkan versi sumber yang lebih mudah dibaca dan versi kompilasi yang lebih efisien. Sebuah benar-benar, benar-benar compiler baik bahkan harus mampu mengubah rekursi normal menjadi rekursi ekor mana yang mungkin.

Pemrograman fungsional lebih tentang " apa " daripada " bagaimana ".

Para pelaksana bahasa akan menemukan cara untuk mengoptimalkan cara kode bekerja di bawahnya, jika kami tidak mencoba membuatnya lebih optimal daripada yang seharusnya. Rekursi juga dapat dioptimalkan dalam bahasa yang mendukung optimisasi panggilan ekor.

Apa yang lebih penting dari sudut pandang programmer adalah keterbacaan dan pemeliharaan daripada optimasi di tempat pertama. Sekali lagi, "optimasi prematur adalah akar dari semua kejahatan".

Ini dugaan. Umumnya rekursi mungkin tidak mengalahkan perulangan sering atau pernah pada masalah ukuran yang layak jika keduanya menggunakan algoritma yang sangat baik (tidak termasuk kesulitan implementasi), mungkin berbeda jika digunakan dengan bahasa dengan rekursi panggilan ekor (dan algoritma rekursif ekor) dan dengan loop juga sebagai bagian dari bahasa) -yang mungkin akan sangat mirip dan bahkan mungkin lebih suka rekursi beberapa waktu.

Menurut teori itu hal yang sama. Rekursi dan putaran dengan kompleksitas O () yang sama akan bekerja dengan kecepatan teoretis yang sama, tetapi tentu saja kecepatan nyata tergantung pada bahasa, kompiler, dan prosesor. Contoh dengan kekuatan angka dapat dikodekan dengan cara iterasi dengan O (ln (n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }