Mengapa loop lebih cepat daripada rekursi?

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?

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.

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$(\lambda x.M)N \leadsto M[N/x]$$[N/x]$$x$$M$$N$$\leadsto$

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.

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.