Mengapa loop lebih cepat daripada rekursi?

17

Dalam praktiknya saya memahami bahwa setiap rekursi dapat ditulis sebagai loop (dan sebaliknya (?)) Dan jika kita mengukur dengan komputer aktual kita menemukan bahwa loop lebih cepat daripada rekursi untuk masalah yang sama. Tetapi apakah ada teori yang membuat perbedaan ini atau apakah itu terutama bersifat empiris?

Niklas
sumber
9
Tampilannya hanya lebih cepat daripada rekursi dalam bahasa yang menerapkannya dengan buruk. Dalam bahasa dengan Rekursi Ekor yang tepat, program rekursif dapat diterjemahkan menjadi loop di belakang layar, dalam hal ini tidak akan ada perbedaan karena mereka identik.
jmite
3
Ya, dan jika Anda menggunakan bahasa yang mendukungnya, Anda dapat menggunakan rekursi (ekor) tanpa memiliki efek kinerja negatif.
jmite
1
@iteite, rekursi ekor yang benar - benar dapat dioptimalkan menjadi satu loop sangat jarang, jauh lebih jarang daripada yang Anda pikirkan. Terutama dalam bahasa yang memiliki jenis yang dikelola seperti variabel yang dihitung referensi.
Johan - mengembalikan Monica
1
Karena Anda termasuk kompleksitas waktu tag, saya merasa saya harus menambahkan bahwa algoritma dengan loop memiliki kompleksitas waktu yang sama dengan algoritma dengan rekursi, tetapi dengan yang terakhir, waktu yang dibutuhkan akan lebih tinggi oleh beberapa faktor konstan, tergantung pada jumlah overhead untuk rekursi.
Lieuwe Vinkhuijzen
2
Hei, karena Anda menambahkan karunia dengan banyak jawaban bagus hampir melelahkan semua kemungkinan, apakah ada sesuatu yang lebih Anda butuhkan atau merasa seperti sesuatu yang harus diklarifikasi? Saya tidak perlu menambahkan banyak, saya dapat mengedit beberapa jawaban atau meninggalkan komentar, jadi ini adalah pertanyaan umum (bukan pribadi).
Evil

Jawaban:

17

Alasan mengapa loop lebih cepat daripada rekursi adalah mudah.
Sebuah loop terlihat seperti ini dalam perakitan.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Satu lompatan bersyarat dan beberapa pembukuan untuk penghitung putaran.

Rekursi (ketika tidak atau tidak dapat dioptimalkan oleh kompiler) terlihat seperti ini:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

Ini jauh lebih kompleks dan Anda mendapatkan setidaknya 3 lompatan (1 tes untuk melihat apakah sudah selesai, satu panggilan dan satu kembali).
Juga dalam rekursi parameter perlu diatur dan diambil.
Tidak satu pun dari hal ini diperlukan dalam satu lingkaran karena semua parameter sudah diatur.

Secara teoritis parameter bisa tetap di tempat dengan rekursi juga, tetapi tidak ada kompiler yang saya tahu benar-benar sejauh itu dalam optimasi mereka.

Perbedaan antara panggilan dan jmp
Pasangan panggilan balik tidak jauh lebih mahal daripada jmp. Pasangan ini mengambil 2 siklus dan jmp mengambil 1; hampir tidak terlihat.
Dalam konvensi pemanggilan yang mendukung parameter register, overhead untuk parameter minimal, tetapi bahkan parameter stack murah selama buffer CPU tidak meluap .
Ini adalah overhead pengaturan panggilan yang ditentukan oleh konvensi panggilan dan penanganan parameter yang digunakan yang memperlambat rekursi.
Ini sangat tergantung implementasi.

Contoh penanganan rekursi yang buruk Sebagai contoh, jika suatu parameter dilewatkan yang dihitung referensi (misalnya parameter tipe yang tidak dikelola) akan menambah siklus 100 melakukan penyesuaian terkunci dari jumlah referensi, benar-benar membunuh kinerja vs loop.
Dalam bahasa yang disetel untuk rekursi perilaku buruk ini tidak terjadi.

Optimasi CPU
Alasan rekursi lainnya lebih lambat adalah karena ia bekerja melawan mekanisme optimisasi di CPU.
Pengembalian hanya dapat diprediksi dengan benar jika jumlah mereka tidak terlalu banyak berturut-turut. CPU memiliki buffer tumpukan kembali dengan beberapa entri. Setelah habis, setiap pengembalian tambahan akan salah duga sehingga menyebabkan keterlambatan yang sangat besar.
Pada setiap CPU yang menggunakan rekursi berbasis stack return buffer call yang melebihi ukuran buffer sebaiknya dihindari.

Tentang contoh kode sepele menggunakan rekursi
Jika Anda menggunakan contoh sepele rekursi seperti Fibonacci jumlah generasi, maka efek ini tidak terjadi, karena setiap compiler yang 'tahu' tentang rekursi akan mengubahnya menjadi lingkaran, sama seperti programmer senilai garam nya akan.
Jika Anda menjalankan contoh-contoh sepele ini dalam lingkungan yang tidak mengoptimalkan dengan benar dari tumpukan panggilan akan (sia-sia) tumbuh di luar batas.

Tentang rekursi ekor
Perhatikan bahwa terkadang kompiler mengoptimalkan rekursi ekor jauh dengan mengubahnya menjadi satu lingkaran. Yang terbaik adalah hanya mengandalkan perilaku ini dalam bahasa yang memiliki rekam jejak yang baik dalam hal ini.
Banyak bahasa menyisipkan kode pembersihan tersembunyi sebelum pengembalian akhir mencegah optimalisasi rekursi ekor.

Kebingungan antara rekursi benar dan semu
Jika lingkungan pemrograman Anda mengubah kode sumber rekursif Anda menjadi sebuah loop, maka itu bisa dibilang bukan rekursi benar yang dieksekusi.
Rekursi sejati membutuhkan penyimpanan remah roti, sehingga rutin rekursif dapat melacak kembali langkah-langkahnya setelah keluar.
Penanganan jejak ini yang membuat rekursi lebih lambat daripada menggunakan loop. Efek ini diperbesar oleh implementasi CPU saat ini seperti diuraikan di atas.

Pengaruh lingkungan pemrograman
Jika bahasa Anda disesuaikan dengan optimalisasi rekursi, maka tentu saja silakan gunakan rekursi di setiap kesempatan. Dalam kebanyakan kasus, bahasa akan mengubah rekursi Anda menjadi semacam lingkaran.
Dalam kasus-kasus di mana tidak bisa, programmer akan kesulitan juga. Jika bahasa pemrograman Anda tidak disetel ke arah rekursi, maka itu harus dihindari kecuali domain tersebut cocok untuk rekursi.
Sayangnya banyak bahasa tidak menangani rekursi dengan baik.

Penyalahgunaan rekursi
Tidak perlu untuk menghitung urutan Fibonacci menggunakan rekursi, pada kenyataannya itu adalah contoh patologis.
Rekursi paling baik digunakan dalam bahasa yang secara eksplisit mendukungnya atau dalam domain tempat rekursi bersinar, seperti penanganan data yang disimpan dalam pohon.

Saya mengerti setiap rekursi dapat ditulis sebagai satu lingkaran

Ya, jika Anda bersedia meletakkan kereta di depan kuda.
Semua instance rekursi dapat ditulis sebagai loop, beberapa instance tersebut mengharuskan Anda untuk menggunakan penyimpanan eksplisit seperti tumpukan.
Jika Anda perlu menggulung tumpukan Anda sendiri hanya untuk mengubah kode rekursif menjadi loop Anda mungkin juga menggunakan rekursi biasa.
Kecuali tentu saja Anda memiliki kebutuhan khusus seperti menggunakan enumerator dalam struktur pohon dan Anda tidak memiliki dukungan bahasa yang tepat.

Johan - mengembalikan Monica
sumber
16

Jawaban-jawaban lain ini agak menyesatkan. Saya setuju bahwa mereka menyatakan detail implementasi yang dapat menjelaskan perbedaan ini, tetapi mereka melebih-lebihkan kasus ini. Seperti yang disarankan dengan benar oleh jmite, mereka berorientasi pada implementasi menuju implementasi yang rusak dari pemanggilan fungsi / rekursi. Banyak bahasa menerapkan loop melalui rekursi, jadi loop jelas tidak akan lebih cepat dalam bahasa tersebut. Rekursi sama sekali tidak seefisien looping (ketika keduanya berlaku) secara teori. Izinkan saya mengutip abstrak dari makalah Guy Steele pada tahun 1977 yang Membongkar Mitos "Panggilan Prosedur Mahal" atau, Implementasi Prosedur yang Dianggap Berbahaya atau, Lambda: the Ultimate GOTO

Cerita rakyat menyatakan bahwa pernyataan GOTO "murah", sementara panggilan prosedur "mahal". Mitos ini sebagian besar merupakan hasil dari implementasi bahasa yang dirancang dengan buruk. Pertumbuhan historis mitos ini dipertimbangkan. Baik ide-ide teoretis dan implementasi yang ada dibahas yang menyanggah mitos ini. Terlihat bahwa penggunaan pemanggilan prosedur yang tidak dibatasi memungkinkan kebebasan gaya yang hebat. Khususnya, diagram alur apa pun dapat ditulis sebagai program "terstruktur" tanpa memperkenalkan variabel tambahan. Kesulitan dengan pernyataan GOTO dan panggilan prosedur ditandai sebagai konflik antara konsep pemrograman abstrak dan konstruksi bahasa yang konkret.

"Konflik antara konsep pemrograman abstrak dan konstruksi bahasa konkret" dapat dilihat dari fakta bahwa sebagian besar model teoretis, misalnya, kalkulus lambda yang tidak diketik , tidak memiliki tumpukan . Tentu saja, konflik ini tidak perlu seperti yang digambarkan oleh makalah di atas dan juga ditunjukkan oleh bahasa yang tidak memiliki mekanisme iterasi selain rekursi seperti Haskell.

fixfix f x = f (fix f) x(λx.M.)NM.[N/x][N/x]xM.N

Sekarang sebagai contoh. Tentukan factsebagai

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Inilah evaluasi fact 3, di mana, untuk kekompakan, saya akan gunakan gsebagai sinonim untuk fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), yaitu fact = g 1. Ini tidak mempengaruhi argumen saya.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Anda dapat melihat dari bentuknya tanpa melihat detail bahwa tidak ada pertumbuhan dan setiap iterasi membutuhkan jumlah ruang yang sama. (Secara teknis, hasil numerik tumbuh yang tidak dapat dihindari dan sama benarnya untuk sebuah whileloop.) Saya menentang Anda untuk menunjukkan "tumpukan" yang tumbuh tanpa batas di sini.

Tampaknya semantik arketipe dari kalkulus lambda sudah melakukan apa yang umumnya disebut "optimisasi panggilan ekor". Tentu saja, tidak ada "optimasi" yang terjadi di sini. Tidak ada aturan khusus di sini untuk panggilan "ekor" yang bertentangan dengan panggilan "normal". Untuk alasan ini, sulit untuk memberikan karakterisasi "abstrak" tentang apa yang dilakukan "optimisasi" panggilan ekor, seperti dalam banyak penokohan abstrak semantik fungsi panggil, tidak ada yang dapat dilakukan "optimasi" panggilan ekor!

Bahwa definisi analog factdalam banyak bahasa "stack overflows", adalah kegagalan oleh bahasa-bahasa tersebut untuk mengimplementasikan semantik panggilan fungsi dengan benar. (Beberapa bahasa memiliki alasan.) Situasi ini kira-kira analog dengan penerapan bahasa yang mengimplementasikan array dengan daftar tertaut. Pengindeksan ke dalam "array" demikian akan menjadi operasi O (n) yang tidak memenuhi harapan array. Jika saya membuat implementasi terpisah dari bahasa, yang menggunakan array nyata dan bukan daftar yang ditautkan, Anda tidak akan mengatakan saya telah mengimplementasikan "optimasi akses array", Anda akan mengatakan saya memperbaiki implementasi array yang rusak.

Jadi, menanggapi jawaban Veedrac. Tumpukan tidak "mendasar" untuk rekursi . Sejauh perilaku "tumpukan-seperti" terjadi selama evaluasi, ini hanya dapat terjadi dalam kasus di mana loop (tanpa struktur data tambahan) tidak akan berlaku di tempat pertama! Dengan kata lain, saya dapat menerapkan loop dengan rekursi dengan karakteristik kinerja yang persis sama. Memang, Skema dan SML keduanya mengandung konstruksi perulangan, tetapi keduanya mendefinisikan mereka dalam hal rekursi (dan, setidaknya dalam Skema, dosering kali diimplementasikan sebagai makro yang berkembang menjadi panggilan rekursif.) Demikian pula, untuk jawaban Johan, tidak ada yang mengatakan kompiler harus memancarkan perakitan yang dijelaskan Johan untuk rekursi. Memang,dengan rakitan yang sama persis apakah Anda menggunakan loop atau rekursi. Satu-satunya waktu kompiler adalah ( agak) wajibuntuk memancarkan perakitan seperti yang dijelaskan Johan adalah ketika Anda melakukan sesuatu yang tidak dapat diungkapkan oleh loop. Sebagaimana diuraikan dalam makalah Steele dan didemonstrasikan oleh praktik nyata bahasa seperti Haskell, Skema, dan SML, bukan "sangat jarang" bahwa panggilan ekor dapat "dioptimalkan", mereka selalu dapat "dioptimalkan". Apakah penggunaan rekursi tertentu akan berjalan dalam ruang konstan tergantung pada bagaimana hal itu ditulis, tetapi batasan yang perlu Anda terapkan untuk memungkinkan itu adalah batasan yang Anda perlukan untuk menyesuaikan masalah Anda ke dalam bentuk lingkaran. (Sebenarnya, mereka kurang ketat. Ada masalah, seperti mesin pengkodean negara, yang lebih bersih dan efisien ditangani melalui panggilan ekor sebagai lawan loop yang akan memerlukan variabel tambahan.) Sekali lagi, membutuhkan lebih banyak pekerjaan adalah ketika kode Anda bukan loop.

Dugaan saya adalah Johan mengacu pada kompiler C yang memiliki batasan sewenang-wenang ketika akan melakukan "optimasi" panggilan ekor. Johan juga mungkin merujuk ke bahasa seperti C ++ dan Rust ketika ia berbicara tentang "bahasa dengan tipe yang dikelola". The RAII idiom dari C ++ dan hadir di Rust juga membuat hal-hal yang dangkal terlihat seperti panggilan ekor, tidak panggilan ekor (karena "destructors" masih perlu dipanggil). Ada proposal untuk menggunakan sintaks yang berbeda untuk memilih ke semantik yang sedikit berbeda yang akan memungkinkan rekursi ekor (yaitu pemanggil panggilan sebelumpanggilan ekor terakhir dan jelas-jelas melarang untuk mengakses benda yang "dihancurkan"). (Pengumpulan sampah tidak memiliki masalah seperti itu, dan semua Haskell, SML, dan Skema adalah bahasa pengumpulan sampah.) Dalam nada yang sangat berbeda, beberapa bahasa, seperti Smalltalk, mengekspos "tumpukan" sebagai objek kelas satu, dalam hal ini huruf "tumpukan" tidak lagi detail implementasi, meskipun ini tidak menghalangi memiliki jenis panggilan terpisah dengan semantik yang berbeda. (Java mengatakan tidak bisa karena cara menangani beberapa aspek keamanan, tetapi ini sebenarnya salah .)

Dalam praktiknya, prevalensi implementasi fungsi yang rusak berasal dari tiga faktor utama. Pertama, banyak bahasa mewarisi implementasi yang rusak dari bahasa implementasi mereka (biasanya C). Kedua, manajemen sumber daya deterministik bagus dan membuat masalah menjadi lebih rumit, meskipun hanya sedikit bahasa yang menawarkan ini. Ketiga, dan, dalam pengalaman saya, alasan kebanyakan orang peduli, adalah bahwa mereka ingin tumpukan jejak ketika kesalahan terjadi untuk keperluan debugging. Hanya alasan kedua adalah alasan yang berpotensi termotivasi secara teoritis.

Derek Elkins meninggalkan SE
sumber
Saya menggunakan "fundamental" untuk merujuk pada alasan paling mendasar bahwa klaim itu benar, bukan pada apakah secara logis harus seperti ini (yang jelas tidak, karena kedua program itu identik identik). Tapi saya tidak setuju dengan komentar Anda secara keseluruhan. Penggunaan kalkulus lambda Anda tidak menghapus tumpukan sebanyak mengaburkannya.
Veedrac
Klaim Anda "Satu-satunya saat kompiler akan (agak) diwajibkan untuk mengeluarkan perakitan seperti yang dijelaskan Johan adalah ketika Anda melakukan sesuatu yang tidak dapat diungkapkan oleh loop." juga cukup aneh; kompiler (biasanya) dapat menghasilkan kode apa pun yang menghasilkan output yang sama, jadi komentar Anda pada dasarnya adalah sebuah tautologi. Tetapi dalam praktiknya kompiler menghasilkan kode yang berbeda untuk program setara yang berbeda, dan pertanyaannya adalah mengapa.
Veedrac
HAI(1)
Untuk memberikan analogi, menjawab pertanyaan mengapa menambahkan string yang tidak dapat diubah dalam loop membutuhkan waktu kuadratik dengan "itu tidak harus" akan sepenuhnya masuk akal, tetapi melanjutkan dengan mengklaim bahwa implementasi itu rusak tidak akan.
Veedrac
Jawaban yang sangat menarik. Meskipun kedengarannya agak seperti kata-kata kasar :-). Terpilih karena saya belajar sesuatu yang baru.
Johan - mengembalikan Monica
2

Pada dasarnya perbedaannya adalah rekursi mencakup tumpukan, struktur data tambahan yang mungkin tidak Anda inginkan, sedangkan loop tidak secara otomatis melakukannya. Hanya dalam kasus-kasus yang jarang terjadi, sebuah kompiler tipikal dapat menyimpulkan bahwa Anda sebenarnya tidak memerlukan stack.

Jika Anda membandingkan alih-alih loop yang beroperasi secara manual pada tumpukan yang dialokasikan (mis. Melalui pointer ke memori tumpukan), Anda biasanya akan menemukan mereka tidak lebih cepat atau bahkan lebih lambat daripada menggunakan tumpukan perangkat keras.

Veedrac
sumber